Enhancing the performance of a dynamically partitionable bus network using a graph coloring algorithm

ABSTRACT

An efficient dynamic graph traversal algorithm is used to identify non-conflicting requests and to allocate network resources in a dynamically partitionable bus network (DPBN). A special processor receives from the control computer of a partitionable bus network an adjacency matrix which indicates conflicts among requests. It applies the dynamic graph traversal algorithm and returns the identified non-conflicting requests to the control computer. The control computer then physically partitions the network into a number of subnetworks for processing non-conflicting requests in parallel. The results of performance evaluation show a forty percent decrease of network delay as compared with a fully utilized, but unpartitioned local area network.

REFERENCES

• 1: C K Baru , S Y W Su, The architecture of SM3: A dynamically partitionable multicomputer system, IEEE Transactions on Computers, v.35 n.9, p.790-802, Sept. 1986 [doi>10.1109/TC.1986.1676839]
• 2: Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
• 3: E. Hafner, Z. Nenadal, and M. Tschanz. A Digital Loop Communication System. IEEE Transactions on Communications, Vol. Com-22, No. 6, June 1974, pp. 877-881.
• 4: IEEE Standard 802.4. Token Passing Bus Access Method and Physical Layer Specifications. Draft D, 1982.
• 5: R. M. Karp. Reducibility among Combinatorial Problems. In R. E. Miller and J. W. Thatcher(eds), Complexity of Computer Computations, Plenum Press, New York, 1972.
• 6: S. Kartashev and S. Kartashev. Dynamic Architecture: Problems and Solutions. Computer, Vol. 11, No. 7, July, 1978, pp. 7-15.
• 7: H. Lam, S. Y. W. Su, F. L. C. Seeger, C. Lee, and W. R. Eisenstadt. A Special Function Unit for Database Operations Within A Data- Control Flow System. Proceedings of the International Conference on Parallel Processing, IEEE, St. Charles, IL. Aug. 1987.
• 8: R. M. Metcalfe, D. R. Botts, C. P. Thacker, and B. W. Lampson. Multipoint Data Communication System with Collision Detection. U.S. Patent 4063220, 1977.
• 9: Joe L. Mott , Abraham Kandel , Theodore P. Baker, Discrete mathematics for computer scientists & mathematicians (2nd ed.), Prentice-Hall, Inc., Upper Saddle River, NJ, 1986
• 10: L Raschid , T Fei , H Lam , S Y W Su, A special-function unit for sorting and sort-based database operations, IEEE Transactions on Computers, v.35 n.12, p.1071-1077, Dec. 1986 [doi>10.1109/TC.1986.1676715]
• 11: S. Y. W. Su and C. K. Baru. Dynamically Partitionable Multicomputers with Switchable Memory. Journal of Parallel and Distributed Computing, Vol. 1, No. 2, Nov. 1984, pp. 152- 184.
• 12: T. K. Woo and S. Y. W. Su. Graph Coloring Algorithms and Their Applications in Resolving Resource Contentions. Submitted to CACM, 1988.
• 13: Tai-Kuo J. Woo , Stanley Y. Su, Improving resource utilization in a partitionable bus network using graph coloring and coin-changing algorithms, 1989

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Computations on discrete structures

Additional Classification:
  C. Computer Systems Organization
  C.1 PROCESSOR ARCHITECTURES
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.5 Local and Wide-Area Networks
          Subjects: Buses

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS

General Terms:
Algorithms, Design, Performance