| Multicomputers are the core technology for many of today's scientific, financial, and commercial applications. Contributions from academia and industry have been shaping the evolution of parallel computing, and address several topics in the areas of parallel hardware architecture and system software design. This dissertation includes research contributions which are relevant to both of these design areas.; The issue of portability of parallel algorithms across distinct networks is addressed first in the dissertation. Research on this subject considers an efficient and flexible parallel programming environment, in which a star graph acts as a host network for hypercube, mesh, and star graph algorithms. As the increasing interest in the star graph may motivate the deployment of multicomputers based on this network, support for an evolutionary library of parallel algorithms becomes a necessity. We address this problem with packing and embedding techniques employing two-level node mapping functions, which significantly reduce the trade-off among performance, resource utilization, and flexibility. We provide a thorough performance characterization for our techniques, which includes metrics such as load, expansion, dilation, average dilation, congestion, and average congestion.; In the area of interconnection networks, we also consider a bounded-degree variant of the star graph, which is referred to as star-connected cycles (SCC). The SCC graph is particularly suited for VLSI-intensive realizations, and is obtained by replacing each node of a star graph with a cycle or ring of nodes. The characterization of SCC graphs given in this dissertation includes topological properties, routing and broadcasting algorithms, and embeddings of meshes into SCCs.; Another contribution of this work is in the area of fault-tolerant clock synchronization for multicomputers. Synchronized clocks are an important operating system service which facilitate, or is required by, many higher level design aspects. We present an interactive convergence algorithm which employs partial clock information dissemination (PCID). PCID reduces the number of messages by orders of magnitude over a conventional interactive convergence algorithm based on reliable all-to-all broadcast of clock values. Our algorithm is the first clock synchronization algorithm employing a novel concept known as multistep interactive convergence. This approach overcomes difficulties the PCID communication model has in handling clock drift, and allows for tolerance of arbitrary faults. The proposed algorithm is applicable to arbitrary-topology multicomputers, and can be combined with a variety of message staggering mechanisms to maintain network contention at a minimum. |
