Dartmouth logo Dartmouth College Computer Science
Technical Report series
CS home
TR home
TR search TR listserv
By author: A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
By number: 2017, 2016, 2015, 2014, 2013, 2012, 2011, 2010, 2009, 2008, 2007, 2006, 2005, 2004, 2003, 2002, 2001, 2000, 1999, 1998, 1997, 1996, 1995, 1994, 1993, 1992, 1991, 1990, 1989, 1988, 1987, 1986

Scheduling Pipelined, Multi-Threaded Programs in Linux
Brunn W. Roysden
Dartmouth TR2004-500


A process causes latency when it performs I/O or communication. Pipelined processes mitigate latency by concurrently executing multiple threads--- sequences of operations--- and overlapping computation, communication, and I/O. When more than one thread is ready to run, the scheduler determines which thread in fact runs. This paper presents techniques for scheduling pipelines, with the following three findings.

First, using Linux kernel version 2.6 and the NPTL threads package, we observe a 3-6% performance improvement over kernel version 2.4 and the LinuxThreads package.

Second, we test techniques that both take advantage of prior knowledge about whether a program is I/O-bound or compute-bound and raise and lower priorities before the pipeline begins working. These techniques, referred to as fixed scheduling, further improve performance by 5% in the case of the compute-bound columnsort algorithm. In the I/O-bound algorithm, fixed scheduling failed to yield better performance than the default scheduling.

Third, we test simple, adjusting methods that do not take advantage of prior knowledge about whether a program in compute-bound or I/O-bound but rather adjust scheduling as the pipeline progresses. These techniques, called adjusting scheduling, fail to yield better performance than the default scheduling in any of our test cases.

In addition, we suggest new scheduling calls and other operating-system improvements.

Note: Senior honors thesis; advisor: Tom Cormen.


Bibliographic citation for this report: [plain text] [BIB] [BibTeX] [Refer]

Or copy and paste:
   Brunn W. Roysden, "Scheduling Pipelined, Multi-Threaded Programs in Linux." Dartmouth Computer Science Technical Report TR2004-500, June 2004.

Notify me about new tech reports.

Search the technical reports.

To receive paper copy of a report, by mail, send your address and the TR number to reports AT cs.dartmouth.edu

Copyright notice: The documents contained in this server are included by the contributing authors as a means to ensure timely dissemination of scholarly and technical work on a non-commercial basis. Copyright and all rights therein are maintained by the authors or by other copyright holders, notwithstanding that they have offered their works here electronically. It is understood that all persons copying this information will adhere to the terms and constraints invoked by each author's copyright. These works may not be reposted without the explicit permission of the copyright holder.

Technical reports collection maintained by David Kotz.