THE VLSI OPTIMALITY OF THE AKS SORTING NETWORK

被引：6

作者：

BILARDI, G

PREPARATA, FP

机构：

[1] Univ of Illinois at, Urbana-Champaign, Coordinated, Science Lab, Urbana, IL, USA, Univ of Illinois at Urbana-Champaign, Coordinated Science Lab, Urbana, IL, USA

来源：

INFORMATION PROCESSING LETTERS | 1985年 / 20卷 / 02期

关键词：

COMPUTER PROGRAMMING - Algorithms - COMPUTER SYSTEMS; DIGITAL - Parallel Processing;

D O I：

10.1016/0020-0190(85)90062-6

中图分类号：

TP [自动化技术、计算机技术];

学科分类号：

0812 ;

摘要：

It is shown that the AKS sorting network can indeed be laid out in area A equals O(n**2), while maintaining an O(log n) computation time, thereby establishing its optimality in the VLSI model of computation.

引用

页码：55 / 59

页数：5

共 11 条

[1]

BILARDI G, 1983, 7TH P C INF SCI SYST, P1

[2]

BILARDI G, 1984, 16TH P SIGACT WASH

[3]

Knuth D. E., 1973, ART COMPUTER PROGRAM

[4]

LEIGHTON FT, 1984, 16TH P SIGACT WASH

[5]

NASSIMI D, 1979, IEEE T COMPUT, V28, P2, DOI 10.1109/TC.1979.1675216

[6]

PREPARATA FP, 1978, IEEE T COMPUT, V27, P669, DOI 10.1109/TC.1978.1675167

[7] SORTING ON A MESH-CONNECTED PARALLEL COMPUTER [J].

THOMPSON, CD ;

KUNG, HT .

COMMUNICATIONS OF THE ACM, 1977, 20 (04) :263-271

[8]

THOMPSON CD, 1983, IEEE T COMPUT, V32

[9]

THOMPSON CD, 1980, THESIS CARNEGIEMELLO

[10]

[No title captured]

← 1 2 →