A multiaccess bus arbitration scheme for VLSI-densed distributed systems

ABSTRACT

A VLSI-densed shared-bus distributed system is a computer system consisting of a large number of VLSI processing units (VPUs) connected to one another by a high-speed bus. Data traffic in such a system is characterized by three distinct features: large population, bursty transmission, and task-dependent accesses with priority. A bus arbitration scheme is required to resolve contentions when several VPUs generate requests simultaneously. Conventional schemes such as daisy chaining, polling, and independent requests are shown to be inadequate. In this paper, a multiaccess code-deciphering (MACD) scheme is proposed. Two versions of the scheme are studied. The first version is a load-dependent scheme that can resolve contentions of N VPUs in an average time of O(log_K/2N) steps where K is equal to the bus width. The second version estimates the number of contending VPUs and resolves contention in a constant average time independent of load. The proposed schemes can support task-dependent accesses with priority.

REFERENCES

• 1: F. A. Briggs , King-Sun Fu , Kai Hwang , B. W. Wah, PUMPS Architecture for Pattern Analysis and Image Database Management, IEEE Transactions on Computers, v.31 n.10, p.969-983, October 1982 [doi>10.1109/TC.1982.1675906]
• 2: H. T. Kung, VLSI Systems and Computations, Springer-Verlag New York, Inc., Secaucus, NJ, 1982
• 3: Control Data Corporation. "Technical Information: Control Data Cyber-plus." News Release and Fact Sheet, Oct. 1983.
• 4: Benjamin W. Wah, A comparative study of distributed resource sharing on multiprocessors, Proceedings of the 10th annual international symposium on Computer architecture, p.301-308c, June 13-17, 1983, Stockholm, Sweden
• 5: Baer, J. Computer Systems Architecture, Rockville, Md.: Computer Science Press, 1980.
• 6: John P. Hayes, Computer architecture and organization; (2nd ed.), McGraw-Hill, Inc., New York, NY, 1988
• 7: Kenneth J. Thurber , E. Douglas Jensen , Larry A. Jack , Larry L. Kinney , Peter C. Patton , Lynn C. Anderson, A systematic approach to the design of digital bussing structures, Proceedings of the December 5-7, 1972, fall joint computer conference, part II, December 05-07, 1972, Anaheim, California [doi>10.1145/1480083.1480094]
• 8: Tobagi, F. A. "Multiaccess Protocols in Packet Communication Systems." IEEE Transactions on Communications, COM-28 (1980), pp. 468--488.
• 9: Wah, B. W. and Y. Y. Juang, "Load Balancing on Local Multiaccess Networks." Proceedings of 8th Conference on Local Computer Networks, Minneapolis, Minn.: IEEE, 1983, pp. 55--61.
• 10: Juang, J. Y., and B. W. Wah. "Unified Window Protocol for Local Multiaccess Networks." Proceedings of Third Annual Joint Conference of the IEEE Computer and Communications Societies. San Francisco, California: IEEE, 1984, pp. 97--104.
• 11: Robert M. Metcalfe , David R. Boggs, Ethernet: distributed packet switching for local computer networks, Communications of the ACM, v.19 n.7, p.395-404, July 1976 [doi>10.1145/360248.360253]