Robert R. McCormick School of Engineering and Applied Science Electrical Engineering and Computer Science Department Center for Ultra-scale Computing and Information Security at Northwestern University

Sponsor:


Project Team Members:

Northwestern University

Syracuse University

Air Force Research Labs


Return to Projects |  CUCIS Home
Project HomeParallel Pipeline Computation ModelInter-task Data RedistributionTask Scheduling and Processor AssignmentMulti-Threading Implementation on Intel Paragon SMP NodesPerformance Results of Parallel Pipeline STAP Implementation

Task Scheduling and Processor Assignment


An important factor in the performance of a parallel system, is how the computational load is mapped onto the compute nodes in the system. Ideally, to achieve maximum parallelism, the load must be evenly distributed across the compute nodes. The problem of statically mapping the workload of a parallel algorithm to the compute nodes in a distributed memory system, has been studied under different problem models, such as [1, 2]. These static mapping policies do not model applications consisting of a sequence of tasks (algorithms), where the output of one task becomes the input to the next task in the sequence.

Optimal use of resources is particularly important in high-performance embedded applications due to limited resources and other constraints such as desired latency or throughput [3]. When several parallel tasks need to be executed in a pipelined fashion, tradeoffs exist between assigning compute nodes to maximize the overall throughput and assigning compute nodes to minimize a single data set's response time (or latency.) The throughput requirement says that when allocating processors to tasks, it should be guaranteed that all the input data sets will be handled in a timely manner. That is, the processing rate should not fall behind the input data rate. The response time criteria, on the other hand, require minimizing the latency of computation on a particular set of data input.

Reference:

  1. M. Berger and S. Bokhari, "A Partitioning Strategy for Nonuniform Problems on Multiprocessors", IEEE Trans. on Computers, 36(5):570-580, May 1987.
  2. F. Berman and L. Snyder, "On Mapping Parallel Algorithms onto Parallel Architectures", Journal of Parallel and Distributed Computing, 4:439-458, 1987.
  3. A. Choudhary and B. Narahari and D. Nicol and R. Simha. "Optimal Processor Assignment for Pipeline Computations", IEEE Trans. on Parallel and Distributed Systems, April, 1994.

Click here to go back

Northwestern University EECS Home | McCormick Home | Northwestern Home | Calendar: Plan-It Purple
© 2011 Robert R. McCormick School of Engineering and Applied Science, Northwestern University
"Tech": 2145 Sheridan Rd, Tech L359, Evanston IL 60208-3118  |  Phone: (847) 491-5410  |  Fax: (847) 491-4455
"Ford": 2133 Sheridan Rd, Ford Building, Rm 3-320, Evanston, IL 60208  |  Fax: (847) 491-5258
Email Director

Last Updated: $LastChangedDate: 2014-09-17 14:51:09 -0500 (Wed, 17 Sep 2014) $