Resource allocation in rectangular SW banyans

ABSTRACT

This paper presents an algorithm for the formation of configurations connecting processors to memory and I/O devices on rectangular SW banyan networks with equivalent processor resources as the base nodes and equivalent memory and I/O resources as the apex nodes. Given a set of resource configuration requests, the algorithm always finds a partition of the network that meets the requests in space and time complexity linear with respect to the number of resources in the network.

REFERENCES

• 1: Batcher, K.E., "The Flip Network in STARAN", Proc. Int'l Conf. on Parallel Processing, August 1976, pp. 65-71.
• 2: Nicos Christofides, Graph theory: An algorithmic approach (Computer science and applied mathematics), Academic Press, Inc., Orlando, FL, 1975
• 3: Dennis, J.B., "The Varieties of Data Flow Computers", Proc. of 1st Int'l Conf. on Distributed Computing Systems, Oct 1979, pp. 430-439.
• 4: Narsingh Deo, Graph Theory with Applications to Engineering and Computer Science (Prentice Hall Series in Automatic Computation), Prentice-Hall, Inc., Upper Saddle River, NJ, 1974
• 5: L. Rodney Goke , G. J. Lipovski, Banyan networks for partitioning multiprocessor systems, Proceedings of the 1st annual symposium on Computer architecture, p.21-28, December 09-11, 1973
• 6: Lang, T., and Stone, H., "A Shuffle Exchange Network with Simplified Control", IEEE Transactions on Computers, C-25, Jan 1976, pp.55-65.
• 7: Lipovski, G.J., and Tripathi, A., "A Reconfigurable Varistructured Array Processor", Proc. of the Int'l Conf. on Parallel Processing, Aug 1977, pp.165-174.
• 8: Lipovski, G.J., and Malek, M., "A Theory for Multicomputer Interconnection Networks", submitted for publication in IEEE Transactions on Computers.
• 9: Pease, M.C., "The Indirect Binary n-Cube Microprocessor Array", IEEE Transactions on Computers, Vol. C-26, May 1977, pp.458-478.
• 10: Premkumar, U.V., Kapur, R., Malek, M., Lipovski, G.J., and Horne, P., "Design and Implementation of the Banyan Network in TRAC", Proc. of the NCC, Vol. 49, May 1980, pp.643-653.
• 11: Premkumar, U.V., A Theoretical Basis for the Analysis and Partitioning of Regular SW Banyans, Ph.D. Thesis, University of Texas at Austin, Aug 1981.
• 12: Siegel, H.J., "Single Instruction Stream - Multiple Data Stream Machine Interconnection Network Design", Proc. of the Int'l Conf. on Parallel Processing, August 1976, pp.273-282.
• 13: Siegel, H.J., "A Model of SIMD Machines and a Comparison of Various Interconnection Networks", IEEE Transactions on Computers, Vol. C-28, No. 12, December 1979, pp.907-917.
• 14: Siegel, H.J., "The Theory Underlying the Partitioning of Permutation Networks", IEEE Transactions on Computers, Vol. C-29, No. 9, September 1980, pp.791-801.
• 15: Wittie, L.D., "Architectures for Large Networks of Microcomputers", Workshop on Interconnection Networks for Parallel and Distributed Processing, Apr 1980, pp.31.
• 16: Wu, C.L., and Feng, T.Y., "The Reverse-Exchange Interconnection Network", Proc. of the Int'l Conf on Parallel Processing, Aug 1979, pp.160-174.

INDEX TERMS

Primary Classification:
  K. Computing Milieux
  K.6 MANAGEMENT OF COMPUTING AND INFORMATION SYSTEMS
      K.6.2 Installation Management
          Subjects: Pricing and resource allocation

Additional Classification:
  B. Hardware
  B.4 INPUT/OUTPUT AND DATA COMMUNICATIONS
      B.4.3 Interconnections (subsystems)

General Terms:
Design, Management