A fast task-to-processor assignment heuristic for real-time multiprocessor DSP applications. (English) Zbl 1026.90054
Summary: The optimal assignment of the tasks to the processors to minimize total delay in a multiprocessor digital signal processing (DSP) architecture is extremely difficult, particularly for systems of many (e.g. 100) tasks. Two factors especially complicate the problem: (1) the multiprocessor architecture affects the inter-processor communication times, and (2) the specific assignment of tasks to processors affects the inter-task communication times. We develop a fast heuristic for assigning tasks to processors. There are two main ingredients in our method: (i) the choice of a useful general-purpose multiprocessor architecture for DSP applications, and (ii) an adaptive list-ordering heuristic which takes advantage of knowledge of the inter-processor communication characteristics of the chosen architecture. Examples are given, including comparisons to exact branch-and-bound methods, and a large sonar example.
MSC:
| 90B80 | Discrete location and assignment |
| 90C59 | Approximation methods and heuristics in mathematical programming |
Keywords:
task assignment; heuristic; critical path analysis; multiprocessor; digital signal processing; mappingReferences:
| [1] | Goubran, R. A.; Hafez, H. M.; Sheikh, A. U.H., Implementation of a real-time mobile channel simulator using a DSP chip, IEEE Transactions on Instrumentation and Measurement, 40, 4, 709-714 (1991) |
| [2] | Kwok, Y. K.; Ahmad, I., Static scheduling algorithms for allocating directed task graphs to multiprocessors, ACM Computing Surveys, 31, 4, 406-471 (1999) |
| [3] | Lee, E. A.; Messerschmitt, D. G., Static scheduling of synchronous data flow programs for digital signal processing, IEEE Transactions on Computers, C-36, 1, 24-35 (1987) · Zbl 0605.68024 |
| [4] | Lee, E. A.; Messerschmitt, D. G., Synchronous data flow, Proceedings of the IEEE, 75, 9, 1235-1245 (1987) |
| [5] | Lee, E. A.; Ho, W. H.; Goei, E. E.; Bier, J. C.; Bhattacharyya, S., Gabriela design environment for DSP, IEEE Transactions on Acoustics, Speech, and Signal Processing, 37, 11, 1751-1762 (1989) |
| [6] | Hu, T. C., Parallel sequencing and assembly line problems, Operations Research, 9, 6, 841-848 (1961) |
| [7] | Coffman, E. G., Computer and job-shop scheduling theory (1976), Wiley: Wiley New York, NY · Zbl 0359.90031 |
| [8] | Lenstra, J. K.; Rinooy Kan, A. H.G., Complexity of scheduling under precedence constraints, Operations Research, 26, 1, 22-35 (1978) · Zbl 0371.90060 |
| [9] | Norman, M. G.; Thanisch, P., Models of machines and computations for mapping in multicomputers, ACM Computing Surveys, 25, 3, 263-302 (1993) |
| [10] | Choudhary, A. N.; Narahari, B.; Nicol, D. M.; Simha, R., Optimal processor assignment for a class of pipelined computations, IEEE Transactions on Parallel and Distributed Systems, 5, 4, 439-445 (1994) |
| [11] | Billionnet, A., Allocating tree structured programs in a distributed system with uniform communication costs, IEEE Transactions on Parallel and Distributed Systems, 5, 4, 445-448 (1994) |
| [12] | Rao, G. S.; Stone, H. S.; Hu, T. C., Assignment of tasks in a distributed processor system with limited memory, IEEE Transactions on Computers, C-28, 4, 291-299 (1979) · Zbl 0397.68024 |
| [13] | Stone, H. S., Multiprocessor scheduling with the aid of network flow algorithms, IEEE Transactions on Software Engineering, SE-3, 1, 85-93 (1977) · Zbl 0355.68042 |
| [14] | Stone, H. S.; Bokhari, S. H., Control of distributed processes, IEEE Computer, 11, 7, 97-106 (1978) |
| [15] | Chu, W. W., Optimal file allocation in a multiple computer system, IEEE Transactions on Computers, C-18, 10, 885-889 (1969) · Zbl 0183.45502 |
| [16] | Efe, K., Heuristic models of task assignment scheduling in distributed systems, IEEE Computer, 15, 6, 50-56 (1982) |
| [17] | Fernandez, E. B.; Ngo, T., Scheduling of task graphs into transputer networks, Congressus Numerantium, 59, 79-88 (1987) · Zbl 0645.68051 |
| [18] | Gonzalez, M. J., Deterministic processor scheduling, ACM Computing Surveys, 9, 3, 173-204 (1977) · Zbl 0357.68069 |
| [19] | Adam, T. L.; Chandy, K. M.; Dichson, J. R., A comparison of list schedules for parallel processing systems, Communications of the ACM, 17, 12, 685-690 (1974) · Zbl 0293.68047 |
| [20] | Conway, R. W.; Maxwell, W. L.; Miller, L. W., Theory of scheduling (1967), Addison-Wesley: Addison-Wesley Reading, MA · Zbl 1058.90500 |
| [21] | Kasahara, H.; Narita, S., Practical multiprocessor scheduling algorithms for efficient parallel processing, IEEE Transactions on Computers, C-33, 11, 1023-1029 (1984) |
| [22] | Manacher, G. K., Production and stabilization of real-time task schedulers, Journal of the ACM, 14, 3, 439-465 (1967) |
| [23] | Ramamoorthy, C. V.; Chandy, K. M.; Gonzalez, M. J., Optimal scheduling strategies in a multiprocessor system, IEEE Transactions on Computers, C-21, 2, 137-146 (1972) · Zbl 0232.68014 |
| [24] | Selvakumar, S.; Siva Ram Murthy, C., Scheduling precedence constrained task graphs with non-negligible intertask communications onto multiprocessors, IEEE Transactions on Parallel and Distributed Systems, 5, 3, 328-336 (1994) |
| [25] | Jain, K. K.; Rajaraman, V., Lower and upper bounds on time for multiprocessor optimal schedules, IEEE Transactions on Parallel and Distributed Systems, 5, 8, 879-886 (1994) |
| [26] | Al-Mouhamed, M. A., Lower bound on the number of processors and time for scheduling precedence graphs with communications costs, IEEE Transactions on Software Engineering, 16, 12, 1390-1401 (1990) |
| [27] | Lavoie M. Task assignment in a DSP multiprocessor environment. Master’s Thesis, Technical Report SCE-90-18, Dept. of Systems and Computer Engineering, Carleton University, Ottawa, Canada, August 1990.; Lavoie M. Task assignment in a DSP multiprocessor environment. Master’s Thesis, Technical Report SCE-90-18, Dept. of Systems and Computer Engineering, Carleton University, Ottawa, Canada, August 1990. |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
