The Diogenes Design Methodology: An Algorithmic Step Toward Efficient Configuration Circuitry
Arnold L. Rosenberg, Judson D. Knott · 1986
DIOGENES is a methodology for designing fault-tolerant VLSI processor arrays. The methodology views the desired array as an undirected graph, with vertices representing processing elements (PEs) and edges representing communication links; the design process operates in two stages: First, the graph representing the desired array is {\em embedded in a book}; then, the book-embedding is converted to an efficient fault-tolerant layout of the array. We describe here one step in the second stage. Specifically, we present here an efficient algorithm that takes a given book-embedding and finds that ``rotation'''' of the embedding that minimizes the number of control bits per PE needed to configure the array to its fault-free format. We illustrate the need for the algorithm by analyzing natural book-embeddings of complete $d$-ary trees and of X-trees. In the case of complete $d$-ary trees, the optimal rotation of the studied book-embeddings requires 2 control bits per PE, while a randomly chosen rotation requires, with probability approaching 1, $log~ _ 2 (d+4)$ control bits. In the case of X-trees, experiments suggest that the algorithm saves approximately one control bit per PE.