New Bounds on Optimal Sorting Networks

被引：13

作者：

Ehlers, Thorsten ^{[1
]}

Mueller, Mike ^{[1
]}

机构：

[1] Univ Kiel, Inst Informat, D-24098 Kiel, Germany

来源：

EVOLVING COMPUTABILITY | 2015年 / 9136卷

关键词：

D O I：

10.1007/978-3-319-20028-6_17

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

We present new parallel sorting networks for 17 to 20 inputs. For 17, 19, and 20 inputs these new networks are faster (i.e., they require fewer computation steps) than the previously known best networks. Therefore, we improve upon the known upper bounds for minimal depth sorting networks on 17, 19, and 20 channels. Furthermore, we show that our sorting network for 17 inputs is optimal in the sense that no sorting network using less layers exists. This solves the main open problem of [D. Bundala & J. Zavodny. Optimal sorting networks, Proc. LATA 2014].

引用

页码：167 / 176

页数：10

共 11 条

[1]

[Anonymous], 1968, P APR 30 MAY 2 1968

[2] AN 11-STEP SORTING NETWORK FOR 18 ELEMENTS [J].

Baddar, Sherenaz W. Al-Haj ;

Batcher, Kenneth E. .

PARALLEL PROCESSING LETTERS, 2009, 19 (01) :97-103

[3]

Bundala D, 2014, LECT NOTES COMPUT SC, V8370, P236, DOI 10.1007/978-3-319-04921-2_19

[4]

Codish M., 2014, CORR

[5] Efficient Filters for the Simulated Evolution of Small Sorting Networks [J].

Coles, Drue .

PROCEEDINGS OF THE FOURTEENTH INTERNATIONAL CONFERENCE ON GENETIC AND EVOLUTIONARY COMPUTATION CONFERENCE, 2012, :593-599

[6]

Knuth D., 1998, ART COMPUTER PROGRAM

[7] Probing-based preprocessing techniques for propositional satisfiability [J].

Lynce, I ;

Marques-Silva, J .

15TH IEEE INTERNATIONAL CONFERENCE ON TOOLS WITH ARTIFICIAL INTELLIGENCE, PROCEEDINGS, 2003, :105-110

[8] A COMPUTER-ASSISTED OPTIMAL DEPTH LOWER BOUND FOR 9-INPUT SORTING NETWORKS [J].

PARBERRY, I .

MATHEMATICAL SYSTEMS THEORY, 1991, 24 (02) :101-116

[9]

Valsalam VK, 2013, J MACH LEARN RES, V14, P303

[10]

[No title captured]

← 1 2 →