Computational Geometry on a Systolic Chip

Bernard Chazelle

doi:10.1109/TC.1984.1676494

Computational Geometry on a Systolic Chip

Bernard Chazelle

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

48 Scopus citations

Abstract

This paper describes systolic algorithms for a number of geometric problems. For the sake of realism we restrict our investigation to one-dimensional arrays whose communication links with the outside are located at the end cells. Implementations yielding maximal throughput are given for solving dynamic versions of convex hull, inclusion, range and intersection search, planar point location, intersection, triangulation, and closest-point problems.

Original language	English (US)
Pages (from-to)	774-785
Number of pages	12
Journal	IEEE Transactions on Computers
Volume	C-33
Issue number	9
DOIs	https://doi.org/10.1109/TC.1984.1676494
State	Published - Sep 1984
Externally published	Yes

All Science Journal Classification (ASJC) codes

Software
Theoretical Computer Science
Hardware and Architecture
Computational Theory and Mathematics

Keywords

Analysis of algorithms
VLSI
computational geometry
convolution
parallel computation
pipelining real-time algorithms
systolic arrays

Access to Document

10.1109/TC.1984.1676494

Cite this

@article{51cd434780b943a7a3a5850e03c27021,

title = "Computational Geometry on a Systolic Chip",

abstract = "This paper describes systolic algorithms for a number of geometric problems. For the sake of realism we restrict our investigation to one-dimensional arrays whose communication links with the outside are located at the end cells. Implementations yielding maximal throughput are given for solving dynamic versions of convex hull, inclusion, range and intersection search, planar point location, intersection, triangulation, and closest-point problems.",

keywords = "Analysis of algorithms, VLSI, computational geometry, convolution, parallel computation, pipelining real-time algorithms, systolic arrays",

author = "Bernard Chazelle",

year = "1984",

month = sep,

doi = "10.1109/TC.1984.1676494",

language = "English (US)",

volume = "C-33",

pages = "774--785",

journal = "IEEE Transactions on Computers",

issn = "0018-9340",

publisher = "IEEE Computer Society",

number = "9",

}

TY - JOUR

T1 - Computational Geometry on a Systolic Chip

AU - Chazelle, Bernard

PY - 1984/9

Y1 - 1984/9

N2 - This paper describes systolic algorithms for a number of geometric problems. For the sake of realism we restrict our investigation to one-dimensional arrays whose communication links with the outside are located at the end cells. Implementations yielding maximal throughput are given for solving dynamic versions of convex hull, inclusion, range and intersection search, planar point location, intersection, triangulation, and closest-point problems.

AB - This paper describes systolic algorithms for a number of geometric problems. For the sake of realism we restrict our investigation to one-dimensional arrays whose communication links with the outside are located at the end cells. Implementations yielding maximal throughput are given for solving dynamic versions of convex hull, inclusion, range and intersection search, planar point location, intersection, triangulation, and closest-point problems.

KW - Analysis of algorithms

KW - VLSI

KW - computational geometry

KW - convolution

KW - parallel computation

KW - pipelining real-time algorithms

KW - systolic arrays

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

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

U2 - 10.1109/TC.1984.1676494

DO - 10.1109/TC.1984.1676494

M3 - Article

AN - SCOPUS:0021500238

SN - 0018-9340

VL - C-33

SP - 774

EP - 785

JO - IEEE Transactions on Computers

JF - IEEE Transactions on Computers

IS - 9

ER -

Computational Geometry on a Systolic Chip

Abstract

All Science Journal Classification (ASJC) codes

Keywords

Access to Document

Other files and links

Fingerprint

Cite this