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

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

Research output: Contribution to journalArticlepeer-review


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 (US)
Pages (from-to)195-215
Number of pages21
JournalInternational Journal of Foundations of Computer Science
Issue number2
StatePublished - Apr 2005
Externally publishedYes

ASJC Scopus subject areas

  • Computer Science (miscellaneous)


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

Cite this