A Heuristic search approach to reduction of connections for multiple-bus organization

Since the cost of the interconnection network grows with the number of buses (due to the connection cost), it becomes natural to try to eliminate as much connections as possible when a large number of processors is involved. The multiple-bus interconnection network is an attractive solution for connecting processors and memory modules in a multiprocessor with shared memory. It provides a throughput which is intermediate between the single bus and the crossbar, with a corresponding intermediate cost. Based in the multibus scheme, this report describes the definition for a heuristic evaluation function to derive optimal reduced configurations. Optimality is evaluated in terms of three parameters of the network, namely, cost (evaluated with respect to the number of connections, memory-module and bus load), reliability (defined as the capability of operation in a degraded form when a bus fail) and load balance in the network. By means of an algorithm which implements the heuristic evaluation function, minimal reduced connection schemes that produce no degradation in throughput and with the best load distribution may be generated. Finally, we conclude that there are Q connection schemes that adequately satisfy these requirements