Paper Details

Reference:

Ronald C. Unrau, Orran Krieger, Ben Gamsa, and and Michael Stumm,
Hierarchical clustering: A structure for scalable multiprocessor operating system design",
Journal of Supercomputing, 9(1-2), March, 1995, pp. 105–134.

Download:

PDF

Abstract:

We introduce the concept of Hierarchical Clustering as a way to structure shared memory multipro- cessor operating systems for scalability. As the name implies, the concept is based on clustering and hierarchical system design. Hierarchical Clustering leads to a modular system, composed of easy-to- design and efficient building blocks. The resulting structure is scalable because it i) maximizes locality, which is key to good performance in NUMA systems, and ii) provides for concurrency that increases linearly with the number of processors. At the same time, there is tight coupling within a cluster, so the system performs well for local interactions which are expected to constitute the common case. A clustered system can easily be adapted to different hardware configurations and architectures by changing the size of the clusters.

We show how this structuring technique is applied to the design of a microkernel-based operating system called HURRICANE. This prototype system is the first complete and running implementation of its kind, and demonstrates the feasibility of a hierarchically clustered system. We present performance results based on the prototype, demonstrating the characteristics and behavior of a clustered system. In particular, we show how clustering trades off the efficiencies of tight coupling for the advantages of replication, increased locality, and decreased lock contention. We describe some of the lessons we learned from our implementation efforts and close with a discussion of our future work.

Keywords:

Operating systems, Shared memory multiprocessors, scalability, Hierarchical design

Reference Info:

DOI: 10.1007/BF01245400
ISSN: 1573-0484 0920-8542
OCLC: 4666173149

BibTeX:

@article(Unrau-JSC95,
    author = {Ronald C. Unrau and Orran Krieger and Ben Gamsa and and Michael Stumm},
    title = {Hierarchical clustering: A structure for scalable multiprocessor operating system design},
    volume = {9},
    number = {1-2},
    month = {March},
    year = {1995},
    pages = {105-134},
    doi = {10.1007/BF01245400},
    issn = {1573-0484 0920-8542},
    keywords = {Operating systems, Shared memory multiprocessors, scalability, Hierarchical design}
)