Title :
Multitasking in multistage interconnection network machines
Author :
Yu, Chansu ; Das, Chita R.
Author_Institution :
Dept. of Electr. Comput. Eng., Pennsylvania State Univ., University Park, PA, USA
Abstract :
Cubic and noncubic task allocation algorithms for multistage-interconnection-network (MIN)-based multiprocessors are presented. Conflicts in passage through the network and inability to partition the system effectively are the main bottlenecks in a MIN-based system. To solve both problems, a renaming scheme called bit reversal (BR) matching pattern is proposed. This matching pattern minimizes conflicts and partitions the system completely into subsystems. Simulation results that show the advantage of allocation algorithms using the proposed matching pattern in terms of system efficiency, delay, and task miss ratio are presented
Keywords :
computational complexity; multiprocessor interconnection networks; multiprogramming; resource allocation; scheduling; allocation algorithms; bit reversal; cubic task allocation algorithms; delay; matching pattern; multistage interconnection network machines; multitasking; noncubic task allocation algorithms; renaming scheme; system completely; system efficiency; task miss ratio; Delay systems; Hypercubes; Intelligent networks; Magnetic heads; Multiprocessor interconnection networks; Multitasking; Partitioning algorithms; Pattern matching; Processor scheduling; Scheduling algorithm;
Conference_Titel :
Distributed Computing Systems, 1992., Proceedings of the 12th International Conference on
Conference_Location :
Yokohama
Print_ISBN :
0-8186-2865-0
DOI :
10.1109/ICDCS.1992.235058
