Quotient Networks

John P. Fishburn; Raphael A. Finkel

doi:10.1109/TC.1982.1675994

Quotient Networks

John P. Fishburn, Raphael A. Finkel

Computer Science

Research output: Contribution to journal › Article › peer-review

64 Scopus citations

Abstract

A large-network algorithm solves a problem of size N on a network of N processors. We present a method for transforming certain large networks into quotient networks that emulate those large networks with fewer processors. Large-network algorithms are easily modified to execute on the quotient network. The emulations result in no loss in execution efficiency. Quotient networks allow algorithms to be designed assuming any number of processors and executed efficiently at a great savings in hardware cost.

Original language	English
Pages (from-to)	288-295
Number of pages	8
Journal	IEEE Transactions on Computers
Volume	C-31
Issue number	4
DOIs	https://doi.org/10.1109/TC.1982.1675994
State	Published - Apr 1982

Keywords

Interconnection networks
SIMD computers
large problem size/machine size
parallel FFT
theory of parallel algorithms

ASJC Scopus subject areas

Software
Theoretical Computer Science
Hardware and Architecture
Computational Theory and Mathematics

Access to Document

10.1109/TC.1982.1675994

Cite this

@article{84448973408643b4addf3b4d115232b7,

title = "Quotient Networks",

abstract = "A large-network algorithm solves a problem of size N on a network of N processors. We present a method for transforming certain large networks into quotient networks that emulate those large networks with fewer processors. Large-network algorithms are easily modified to execute on the quotient network. The emulations result in no loss in execution efficiency. Quotient networks allow algorithms to be designed assuming any number of processors and executed efficiently at a great savings in hardware cost.",

keywords = "Interconnection networks, SIMD computers, large problem size/machine size, parallel FFT, theory of parallel algorithms",

author = "Fishburn, {John P.} and Finkel, {Raphael A.}",

year = "1982",

month = apr,

doi = "10.1109/TC.1982.1675994",

language = "English",

volume = "C-31",

pages = "288--295",

number = "4",

}

TY - JOUR

T1 - Quotient Networks

AU - Fishburn, John P.

AU - Finkel, Raphael A.

PY - 1982/4

Y1 - 1982/4

N2 - A large-network algorithm solves a problem of size N on a network of N processors. We present a method for transforming certain large networks into quotient networks that emulate those large networks with fewer processors. Large-network algorithms are easily modified to execute on the quotient network. The emulations result in no loss in execution efficiency. Quotient networks allow algorithms to be designed assuming any number of processors and executed efficiently at a great savings in hardware cost.

AB - A large-network algorithm solves a problem of size N on a network of N processors. We present a method for transforming certain large networks into quotient networks that emulate those large networks with fewer processors. Large-network algorithms are easily modified to execute on the quotient network. The emulations result in no loss in execution efficiency. Quotient networks allow algorithms to be designed assuming any number of processors and executed efficiently at a great savings in hardware cost.

KW - Interconnection networks

KW - SIMD computers

KW - large problem size/machine size

KW - parallel FFT

KW - theory of parallel algorithms

UR - http://www.scopus.com/inward/record.url?scp=0020114780&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0020114780&partnerID=8YFLogxK

U2 - 10.1109/TC.1982.1675994

DO - 10.1109/TC.1982.1675994

M3 - Article

AN - SCOPUS:0020114780

SN - 0018-9340

VL - C-31

SP - 288

EP - 295

JO - IEEE Transactions on Computers

JF - IEEE Transactions on Computers

IS - 4

ER -

Quotient Networks

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this