Improving resource utilization in a partitionable bus network using graph coloring and coin-changing algorithms
Tai-Kuo J. Woo, Stanley Y. W. Su · University of Florida Digital Collections (University of Florida) · 1989
Achieving efficiency in a parallel processing environment is a fundamental problem in many computer science and engineering disciplines. In a large scale computer system, resources such as memory, secondary devices, and communication networks are usually shared by processors and processes. Resource contentions often occur, and system performance is degraded due to blocking and deadlock problems. System performance can be improved by detecting non-conflicting processes and scheduling them for parallel processing. In this dissertation, we introduce three graph coloring algorithms for distinguishing conflicting and non-conflicting processes. The complexity of each algorithm is O(E), where E is the number of edges of the graph. By interpreting the results of the graph traversal algorithm, non-conflicting processes can be scheduled for parallel communication or processing. Another problem dealt with in this work is the idling problem in the execution of non-conflicting processes. Since the processes may take different amount of times to execute, if processors are assigned to process them to their completion, the processors of shorter processes will be idle after the completion of their tasks. In this dissertation, a coin-changing algorithm is applied to achieve better scheduling of non-conflicting processes. Both the graph traversal algorithms and coin-changing algorithms are then applied in a dynamically partitionable bus network to demonstrate that non-conflicting communication requests can be identified and scheduled for execution in partitioned subnetworks. The performance of a dynamically partitionable bus network using these algorithms is evaluated. This work makes the following specific contributions. First, it introduces and analyzes three graph coloring algorithms and their performance. An analytical study shows that the dynamic graph traversal algorithm has better performance than other existing graph coloring algorithms. Second, it presents a design of a hardware for implementing the dynamic graph traversal algorithm to meet the time requirement of some real-time environment. Third, it demonstrates the utility of the graph traversal algorithms in a partitionable bus network by analysis and simulation. Fourth, it provides an analysis of a coin-changing algorithm and its application to solve the bus idling problem in a partitionable bus network.