PCBN - A HIGH-PERFORMANCE PARTITIONABLE CIRCULAR BUS NETWORK FOR DISTRIBUTED SYSTEMS

In a distributed computing environment, a highperformance communicatio n network is essential. In this paper, we present a dynamically partit ionable circular bus network (PCBN) and efficient algorithms for maxim izing its utilization. In our approach, a distributed network is trans formed into a graph, in which a vertex represents a communication requ est and an edge denotes the conflict between a pair of communication r equests. A graph traversal algorithm is then applied to the graph to i dentify some maximal independent sets of vertices, The communication r equests corresponding to the vertices of a maximal independent set can proceed in parallel. By computing the expected size of the maximal in dependent sets of a graph, we can obtain the improvement ratio of the network. In this paper, the network control and synchronization techni ques of PCBN are described in detail. Another problem dealt with in th is paper is the idling problem in the execution of nonconflicting requ ests. Since the requests may take different amounts of time to execute , the subnetworks of shorter durations will be idle after the completi on of their requests if subnetworks are assigned to process them to th eir completion. This bus idling problem is solved by using a coin-chan ging algorithm. The performance evaluation shows a significant decreas e in network delay.