A Performance Bound of Multistage Combining Networks

Gyungho Lee

Research output: Contribution to journalArticlepeer-review

17 Citations (Scopus)


Concurrent requests by many processors to a shared variable on a shared memory machine can create contention that will be serious enough to stall large machines. “Combining,” in which several requests for the same variable can be combined into a single request, has been suggested as an effective method of alleviating this contention. “Multistage combining network” is a multistage interconnection network in which each switching node can perform combining. In this paper, a bound on the delays in multistage combining networks is developed by considering an idealized combining under “hot spot” traffic. Our result states that multistage combining networks are “stable” at least in theory under hot spot traffic. We also discuss some problems in achieving such stability in practice.

Original languageEnglish
Pages (from-to)1387-1395
Number of pages9
JournalIEEE Transactions on Computers
Issue number10
Publication statusPublished - 1989 Oct


  • Buffered network
  • combining
  • hot spots
  • multiprocessors
  • multistage interconnection networks
  • parallel processing
  • performance analysis
  • supercomputing

ASJC Scopus subject areas

  • Software
  • Theoretical Computer Science
  • Hardware and Architecture
  • Computational Theory and Mathematics


Dive into the research topics of 'A Performance Bound of Multistage Combining Networks'. Together they form a unique fingerprint.

Cite this