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

fYear

1992

fDate

9-12 Jun 1992

Firstpage

30

Lastpage

37

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;

fLanguage

English

Publisher

ieee

Conference_Titel

Distributed Computing Systems, 1992., Proceedings of the 12th International Conference on

Conference_Location

Yokohama

Print_ISBN

0-8186-2865-0

Type

conf

DOI

10.1109/ICDCS.1992.235058

Filename

235058