Loading…

A unified algorithm for sorting on multidimensional mesh-connected processors

A new algorithm is proposed for sorting on multidimensional meshes. The algorithm, called MeshSort, is significant in that it is a general algorithm that unifies 2 well-known algorithms that operate on special cases of the multidimensional mesh: 1. Bitonic sort on the binary hypercube, and 2. Shears...

Full description

Saved in:

Bibliographic Details
Published in:	Information processing letters 1991-02, Vol.37 (4), p.225-231
Main Authors:	Corbett, Peter F., Scherson, Isaac D.
Format:	Article
Language:	English
Subjects:	Algorithms Applied sciences Bitonic sort Computer programming Computer science Computer science control theory systems Exact sciences and technology Functions Hypermesh Mathematical models MeshSort Multiprocessing parallel algorithms Parallel processing Shearsort Software Theory Utility programs
Citations:	Items that this one cites Items that cite this one
Online Access:	Get full text
Tags:	Add Tag No Tags, Be the first to tag this record!

cited_by	cdi_FETCH-LOGICAL-c392t-66977801b4cba5c02f4a5a0a132856c5c10b55527421922f2c798ed1fad9b4153
cites	cdi_FETCH-LOGICAL-c392t-66977801b4cba5c02f4a5a0a132856c5c10b55527421922f2c798ed1fad9b4153
container_end_page	231
container_issue	4
container_start_page	225
container_title	Information processing letters
container_volume	37
creator	Corbett, Peter F. Scherson, Isaac D.
description	A new algorithm is proposed for sorting on multidimensional meshes. The algorithm, called MeshSort, is significant in that it is a general algorithm that unifies 2 well-known algorithms that operate on special cases of the multidimensional mesh: 1. Bitonic sort on the binary hypercube, and 2. Shearsort on the 2-dimensional mesh. Both Bitonic sort on a hypercube and Shearsort are shown to be special cases of MeshSort. MeshSort operates on meshes of any size and dimension. An indexing scheme is introduced that is a hybrid of the major and the snake-like indexing schemes. MeshSort is described in terms of the indexing scheme and simple sorting instructions. This provides a powerful technique for describing recursive and iterative multidimensional mesh algorithms in a concise manner. Like Bitonic sort and Shearsort, MeshShort is nonoptimal.
doi_str_mv	10.1016/0020-0190(91)90193-L
format	article
fullrecord	<record><control><sourceid>proquest_cross</sourceid><recordid>TN_cdi_proquest_miscellaneous_25308702</recordid><sourceformat>XML</sourceformat><sourcesystem>PC</sourcesystem><els_id>002001909190193L</els_id><sourcerecordid>1137335</sourcerecordid><originalsourceid>FETCH-LOGICAL-c392t-66977801b4cba5c02f4a5a0a132856c5c10b55527421922f2c798ed1fad9b4153</originalsourceid><addsrcrecordid>eNp9kE1LxDAQhoMouK7-Aw9FUPRQnUmbprkIIn7Bihc9h2yarpE2WZNW8N-bdRcFD55mDs_7DvMQcohwjoDVBQCFHFDAqcAzkZYin22RCdac5hWi2CaTH2SX7MX4BgBVWfAJebzKRmdba5pMdQsf7PDaZ60PWfRhsG6ReZf1YzfYxvbGReud6rLexNdce-eMHlJwGbw2MQXiPtlpVRfNwWZOycvtzfP1fT57unu4vprluhB0yKtKcF4Dzks9V0wDbUvFFCgsaM0qzTTCnDFGeUlRUNpSzUVtGmxVI-YlsmJKTta96fT7aOIgexu16TrljB-jpKyAmgNN4NEf8M2PIf2QmIJTTqFetZVrSAcfYzCtXAbbq_ApEeRKsFzZkyt7UqD8FixnKXa86VZRq64Nymkbf7OiZBShTNzlmjPJyIc1QUZtjdOmsSEJlI23_x_6AgMejgU</addsrcrecordid><sourcetype>Aggregation Database</sourcetype><iscdi>true</iscdi><recordtype>article</recordtype><pqid>237272085</pqid></control><display><type>article</type><title>A unified algorithm for sorting on multidimensional mesh-connected processors</title><source>Backfile Package - Computer Science (Legacy) [YCS]</source><source>Backfile Package - Mathematics (Legacy) [YMT]</source><creator>Corbett, Peter F. ; Scherson, Isaac D.</creator><creatorcontrib>Corbett, Peter F. ; Scherson, Isaac D.</creatorcontrib><description>A new algorithm is proposed for sorting on multidimensional meshes. The algorithm, called MeshSort, is significant in that it is a general algorithm that unifies 2 well-known algorithms that operate on special cases of the multidimensional mesh: 1. Bitonic sort on the binary hypercube, and 2. Shearsort on the 2-dimensional mesh. Both Bitonic sort on a hypercube and Shearsort are shown to be special cases of MeshSort. MeshSort operates on meshes of any size and dimension. An indexing scheme is introduced that is a hybrid of the major and the snake-like indexing schemes. MeshSort is described in terms of the indexing scheme and simple sorting instructions. This provides a powerful technique for describing recursive and iterative multidimensional mesh algorithms in a concise manner. Like Bitonic sort and Shearsort, MeshShort is nonoptimal.</description><identifier>ISSN: 0020-0190</identifier><identifier>EISSN: 1872-6119</identifier><identifier>DOI: 10.1016/0020-0190(91)90193-L</identifier><identifier>CODEN: IFPLAT</identifier><language>eng</language><publisher>Amsterdam: Elsevier B.V</publisher><subject>Algorithms ; Applied sciences ; Bitonic sort ; Computer programming ; Computer science ; Computer science; control theory; systems ; Exact sciences and technology ; Functions ; Hypermesh ; Mathematical models ; MeshSort ; Multiprocessing ; parallel algorithms ; Parallel processing ; Shearsort ; Software ; Theory ; Utility programs</subject><ispartof>Information processing letters, 1991-02, Vol.37 (4), p.225-231</ispartof><rights>1991</rights><rights>1991 INIST-CNRS</rights><rights>Copyright Elsevier Sequoia S.A. Feb 28, 1991</rights><lds50>peer_reviewed</lds50><woscitedreferencessubscribed>false</woscitedreferencessubscribed><citedby>FETCH-LOGICAL-c392t-66977801b4cba5c02f4a5a0a132856c5c10b55527421922f2c798ed1fad9b4153</citedby><cites>FETCH-LOGICAL-c392t-66977801b4cba5c02f4a5a0a132856c5c10b55527421922f2c798ed1fad9b4153</cites></display><links><openurl>$$Topenurl_article</openurl><openurlfulltext>$$Topenurlfull_article</openurlfulltext><thumbnail>$$Tsyndetics_thumb_exl</thumbnail><linktohtml>$$Uhttps://www.sciencedirect.com/science/article/pii/002001909190193L$$EHTML$$P50$$Gelsevier$$H</linktohtml><link.rule.ids>314,780,784,3429,3564,27924,27925,45972,46003</link.rule.ids><backlink>$$Uhttp://pascal-francis.inist.fr/vibad/index.php?action=getRecordDetail&idt=19452104$$DView record in Pascal Francis$$Hfree_for_read</backlink></links><search><creatorcontrib>Corbett, Peter F.</creatorcontrib><creatorcontrib>Scherson, Isaac D.</creatorcontrib><title>A unified algorithm for sorting on multidimensional mesh-connected processors</title><title>Information processing letters</title><description>A new algorithm is proposed for sorting on multidimensional meshes. The algorithm, called MeshSort, is significant in that it is a general algorithm that unifies 2 well-known algorithms that operate on special cases of the multidimensional mesh: 1. Bitonic sort on the binary hypercube, and 2. Shearsort on the 2-dimensional mesh. Both Bitonic sort on a hypercube and Shearsort are shown to be special cases of MeshSort. MeshSort operates on meshes of any size and dimension. An indexing scheme is introduced that is a hybrid of the major and the snake-like indexing schemes. MeshSort is described in terms of the indexing scheme and simple sorting instructions. This provides a powerful technique for describing recursive and iterative multidimensional mesh algorithms in a concise manner. Like Bitonic sort and Shearsort, MeshShort is nonoptimal.</description><subject>Algorithms</subject><subject>Applied sciences</subject><subject>Bitonic sort</subject><subject>Computer programming</subject><subject>Computer science</subject><subject>Computer science; control theory; systems</subject><subject>Exact sciences and technology</subject><subject>Functions</subject><subject>Hypermesh</subject><subject>Mathematical models</subject><subject>MeshSort</subject><subject>Multiprocessing</subject><subject>parallel algorithms</subject><subject>Parallel processing</subject><subject>Shearsort</subject><subject>Software</subject><subject>Theory</subject><subject>Utility programs</subject><issn>0020-0190</issn><issn>1872-6119</issn><fulltext>true</fulltext><rsrctype>article</rsrctype><creationdate>1991</creationdate><recordtype>article</recordtype><recordid>eNp9kE1LxDAQhoMouK7-Aw9FUPRQnUmbprkIIn7Bihc9h2yarpE2WZNW8N-bdRcFD55mDs_7DvMQcohwjoDVBQCFHFDAqcAzkZYin22RCdac5hWi2CaTH2SX7MX4BgBVWfAJebzKRmdba5pMdQsf7PDaZ60PWfRhsG6ReZf1YzfYxvbGReud6rLexNdce-eMHlJwGbw2MQXiPtlpVRfNwWZOycvtzfP1fT57unu4vprluhB0yKtKcF4Dzks9V0wDbUvFFCgsaM0qzTTCnDFGeUlRUNpSzUVtGmxVI-YlsmJKTta96fT7aOIgexu16TrljB-jpKyAmgNN4NEf8M2PIf2QmIJTTqFetZVrSAcfYzCtXAbbq_ApEeRKsFzZkyt7UqD8FixnKXa86VZRq64Nymkbf7OiZBShTNzlmjPJyIc1QUZtjdOmsSEJlI23_x_6AgMejgU</recordid><startdate>19910228</startdate><enddate>19910228</enddate><creator>Corbett, Peter F.</creator><creator>Scherson, Isaac D.</creator><general>Elsevier B.V</general><general>Elsevier Science</general><general>Elsevier Sequoia S.A</general><scope>IQODW</scope><scope>AAYXX</scope><scope>CITATION</scope><scope>7SC</scope><scope>8FD</scope><scope>JQ2</scope><scope>L7M</scope><scope>L~C</scope><scope>L~D</scope></search><sort><creationdate>19910228</creationdate><title>A unified algorithm for sorting on multidimensional mesh-connected processors</title><author>Corbett, Peter F. ; Scherson, Isaac D.</author></sort><facets><frbrtype>5</frbrtype><frbrgroupid>cdi_FETCH-LOGICAL-c392t-66977801b4cba5c02f4a5a0a132856c5c10b55527421922f2c798ed1fad9b4153</frbrgroupid><rsrctype>articles</rsrctype><prefilter>articles</prefilter><language>eng</language><creationdate>1991</creationdate><topic>Algorithms</topic><topic>Applied sciences</topic><topic>Bitonic sort</topic><topic>Computer programming</topic><topic>Computer science</topic><topic>Computer science; control theory; systems</topic><topic>Exact sciences and technology</topic><topic>Functions</topic><topic>Hypermesh</topic><topic>Mathematical models</topic><topic>MeshSort</topic><topic>Multiprocessing</topic><topic>parallel algorithms</topic><topic>Parallel processing</topic><topic>Shearsort</topic><topic>Software</topic><topic>Theory</topic><topic>Utility programs</topic><toplevel>peer_reviewed</toplevel><toplevel>online_resources</toplevel><creatorcontrib>Corbett, Peter F.</creatorcontrib><creatorcontrib>Scherson, Isaac D.</creatorcontrib><collection>Pascal-Francis</collection><collection>CrossRef</collection><collection>Computer and Information Systems Abstracts</collection><collection>Technology Research Database</collection><collection>ProQuest Computer Science Collection</collection><collection>Advanced Technologies Database with Aerospace</collection><collection>Computer and Information Systems Abstracts Academic</collection><collection>Computer and Information Systems Abstracts Professional</collection><jtitle>Information processing letters</jtitle></facets><delivery><delcategory>Remote Search Resource</delcategory><fulltext>fulltext</fulltext></delivery><addata><au>Corbett, Peter F.</au><au>Scherson, Isaac D.</au><format>journal</format><genre>article</genre><ristype>JOUR</ristype><atitle>A unified algorithm for sorting on multidimensional mesh-connected processors</atitle><jtitle>Information processing letters</jtitle><date>1991-02-28</date><risdate>1991</risdate><volume>37</volume><issue>4</issue><spage>225</spage><epage>231</epage><pages>225-231</pages><issn>0020-0190</issn><eissn>1872-6119</eissn><coden>IFPLAT</coden><abstract>A new algorithm is proposed for sorting on multidimensional meshes. The algorithm, called MeshSort, is significant in that it is a general algorithm that unifies 2 well-known algorithms that operate on special cases of the multidimensional mesh: 1. Bitonic sort on the binary hypercube, and 2. Shearsort on the 2-dimensional mesh. Both Bitonic sort on a hypercube and Shearsort are shown to be special cases of MeshSort. MeshSort operates on meshes of any size and dimension. An indexing scheme is introduced that is a hybrid of the major and the snake-like indexing schemes. MeshSort is described in terms of the indexing scheme and simple sorting instructions. This provides a powerful technique for describing recursive and iterative multidimensional mesh algorithms in a concise manner. Like Bitonic sort and Shearsort, MeshShort is nonoptimal.</abstract><cop>Amsterdam</cop><pub>Elsevier B.V</pub><doi>10.1016/0020-0190(91)90193-L</doi><tpages>7</tpages></addata></record>
fulltext	fulltext
identifier	ISSN: 0020-0190
ispartof	Information processing letters, 1991-02, Vol.37 (4), p.225-231
issn	0020-0190 1872-6119
language	eng
recordid	cdi_proquest_miscellaneous_25308702
source	Backfile Package - Computer Science (Legacy) [YCS]; Backfile Package - Mathematics (Legacy) [YMT]
subjects	Algorithms Applied sciences Bitonic sort Computer programming Computer science Computer science control theory systems Exact sciences and technology Functions Hypermesh Mathematical models MeshSort Multiprocessing parallel algorithms Parallel processing Shearsort Software Theory Utility programs
title	A unified algorithm for sorting on multidimensional mesh-connected processors
url	http://sfxeu10.hosted.exlibrisgroup.com/loughborough?ctx_ver=Z39.88-2004&ctx_enc=info:ofi/enc:UTF-8&ctx_tim=2024-12-28T19%3A58%3A40IST&url_ver=Z39.88-2004&url_ctx_fmt=infofi/fmt:kev:mtx:ctx&rfr_id=info:sid/primo.exlibrisgroup.com:primo3-Article-proquest_cross&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.genre=article&rft.atitle=A%20unified%20algorithm%20for%20sorting%20on%20multidimensional%20mesh-connected%20processors&rft.jtitle=Information%20processing%20letters&rft.au=Corbett,%20Peter%20F.&rft.date=1991-02-28&rft.volume=37&rft.issue=4&rft.spage=225&rft.epage=231&rft.pages=225-231&rft.issn=0020-0190&rft.eissn=1872-6119&rft.coden=IFPLAT&rft_id=info:doi/10.1016/0020-0190(91)90193-L&rft_dat=%3Cproquest_cross%3E1137335%3C/proquest_cross%3E%3Cgrp_id%3Ecdi_FETCH-LOGICAL-c392t-66977801b4cba5c02f4a5a0a132856c5c10b55527421922f2c798ed1fad9b4153%3C/grp_id%3E%3Coa%3E%3C/oa%3E%3Curl%3E%3C/url%3E&rft_id=info:oai/&rft_pqid=237272085&rft_id=info:pmid/&rfr_iscdi=true