Dynamic, distributed resource allocation on regular SW-banyans




Feo, John T., 1955-

Journal Title

Journal ISSN

Volume Title



In order to achieve the orders-of-magnitude increases in speed and fault tolerance desired by many of today's users, it is necessary to execute the parallel subtasks of processes concurrently. A class of computer systems able to achieve such high-performance parallel computing is configurable multiprocessors. Such systems can be both flexible and fast; however, the degree to which they are is determined by the properties of their interconnection networks and the efficiency and robustness of the algorithms used to configure the networks into disjoint subsystems each with the resources and the architecture desired by the intended user. This dissertation establishes a basis for configuring regular SW-banyans (a large class of configurable networks) which is both theoretically sound and practical in the context of an existing system, such as the Texas Reconfigurable Array Computer. In addition, specific algorithms to construct a wide variety of architectures on regular SW-banyans are presented. These algorithms are dynamic, distributed, of complexity N Log N or better and work correctly in the presence of faults