An algorithmic model for heterogeneous hyper-clusters: Rationale and experience

Franck Cappello*, Pierre Fraigniaud, Bernard Mans, Arnold L. Rosenberg

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

19 Citations (Scopus)

Abstract

A formal model of hyperclusters of processors - that is, clusters of clusters of ... of clusters of processors - is formulated. The model characterizes a hypercluster H via a suite of parameters that expose the computational and communicational powers of H's constituent processors and networks. The hyperclusters studied enjoy heterogeneity along three orthogonal axes. (1) The processors that populate a hypercluster may differ in computational powers (speed of computation and memory access). (2) The clusters comprising a hypercluster are organized hierarchically and are interconnected via a hierarchy of networks of possibly differing bandwidths and speeds. (3) The clusters at each level of the hierarchy may differ in sizes. The resulting HiHCoHP model is rather detailed, exposing architectural features such as the bandwidth and transit costs of both networks and their ports. The algorithmic tractability of the model is demonstrated by reviewing two case studies that use the model to study heterogeneous clusters (HNOWs, for short). The first study develops an algorithm for the trigger-broadcast problem in HNOWs, in which a broadcast "triggers" personalized computations at each node of the cluster. The algorithm is predictably efficient in general and is actually optimal in special circumstances. The second study develops an asymptotically optimal algorithm for sharing a large "bag of tasks" within an HNOW.

Original languageEnglish
Pages (from-to)195-215
Number of pages21
JournalInternational Journal of Foundations of Computer Science
Volume16
Issue number2
DOIs
Publication statusPublished - Apr 2005

Fingerprint Dive into the research topics of 'An algorithmic model for heterogeneous hyper-clusters: Rationale and experience'. Together they form a unique fingerprint.

Cite this