Parallel Prefix Computation and Sorting on a Recursive Dual-Net

In this paper, we propose efficient algorithms for parallel prefix computation and sorting on a recursive dual-net. The recursive dual-net RDN^k(B) for k > 0 has (2n_o)^(2K)/2 nodes and d_0 + k links per node, where n_0 and d_0 are the number of nodes and the node-degree of the base-network B, re...

Full description

Saved in:
Bibliographic Details
Published in:Journal of information processing systems 2011, 7(2), 20, pp.271-286
Main Authors: Yamin Li, Shietung Peng, Wanming Chu
Format: Article
Language:English
Subjects:
컴퓨터학
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
cited_by
cites
container_end_page 286
container_issue
container_start_page 271
container_title Journal of information processing systems
container_volume
creator Yamin Li
Shietung Peng
Wanming Chu
description In this paper, we propose efficient algorithms for parallel prefix computation and sorting on a recursive dual-net. The recursive dual-net RDN^k(B) for k > 0 has (2n_o)^(2K)/2 nodes and d_0 + k links per node, where n_0 and d_0 are the number of nodes and the node-degree of the base-network B, respectively. Assume that each node holds one data item, the communication and computation time complexities of the algorithm for parallel prefix computation on RDN^k(B), k > 0, are 2^(k+1)-2+2^kT_(comm)(0) and 2^(k+1)-2+2^kT_(comp)(0), respectively, where T_(comm)(0) and T_(comp)(0) are the communication and computation time complexities of the algorithm for parallel prefix computation on the base-network B, respectively. The algorithm for parallel sorting on RDN^k(B) is restricted on B = Q_m where Q_m is an m-cube. Assume that each node holds a single data item, the sorting algorithm runs in O((m2^k)^2) computation steps and O((km2^k)^2) communication steps, respectively. KCI Citation Count: 0
doi_str_mv 10.3745/JIPS.2011.7.2.271
format article
fullrecord <record><control><sourceid>nrf</sourceid><recordid>TN_cdi_nrf_kci_oai_kci_go_kr_ARTI_226121</recordid><sourceformat>XML</sourceformat><sourcesystem>PC</sourcesystem><sourcerecordid>oai_kci_go_kr_ARTI_226121</sourcerecordid><originalsourceid>FETCH-LOGICAL-c203t-937616e0f6e81c055349ec89ead249ea6338d62ea01f46a9ca19a7f181c9d5623</originalsourceid><addsrcrecordid>eNotjF1LwzAYRoMoWKc_wLtcepOaN2mT5krG_KoMLduE3ZWXNBlxtZW0FX--8-PqPAceDiGXwFOps_z6qazWqeAAqU5FKjQckURwI1jB8-0xScBoxQzI7Sk5G4Y3zlWhTZaQmwojtq1raRWdD1900b9_TCOOoe8odg1d93EM3Y7-KF05O8UhfDp6O2HLnt14Tk48toO7-OeMvN7fbRaPbPnyUC7mS2YFlyMzUitQjnvlCrA8z2VmnC2Mw0YcFiopi0YJhxx8ptBYBIPaw-FsmlwJOSNXf90u-npvQ91j-OWur_exnq82ZS2EAgHyG1VbTIM</addsrcrecordid><sourcetype>Open Website</sourcetype><iscdi>true</iscdi><recordtype>article</recordtype></control><display><type>article</type><title>Parallel Prefix Computation and Sorting on a Recursive Dual-Net</title><source>Free E-Journal (出版社公開部分のみ）</source><creator>Yamin Li ; Shietung Peng ; Wanming Chu</creator><creatorcontrib>Yamin Li ; Shietung Peng ; Wanming Chu</creatorcontrib><description>In this paper, we propose efficient algorithms for parallel prefix computation and sorting on a recursive dual-net. The recursive dual-net RDN^k(B) for k &gt; 0 has (2n_o)^(2K)/2 nodes and d_0 + k links per node, where n_0 and d_0 are the number of nodes and the node-degree of the base-network B, respectively. Assume that each node holds one data item, the communication and computation time complexities of the algorithm for parallel prefix computation on RDN^k(B), k &gt; 0, are 2^(k+1)-2+2^kT_(comm)(0) and 2^(k+1)-2+2^kT_(comp)(0), respectively, where T_(comm)(0) and T_(comp)(0) are the communication and computation time complexities of the algorithm for parallel prefix computation on the base-network B, respectively. The algorithm for parallel sorting on RDN^k(B) is restricted on B = Q_m where Q_m is an m-cube. Assume that each node holds a single data item, the sorting algorithm runs in O((m2^k)^2) computation steps and O((km2^k)^2) communication steps, respectively. KCI Citation Count: 0</description><identifier>ISSN: 1976-913X</identifier><identifier>EISSN: 2092-805X</identifier><identifier>DOI: 10.3745/JIPS.2011.7.2.271</identifier><language>eng</language><publisher>한국정보처리학회</publisher><subject>컴퓨터학</subject><ispartof>JIPS(Journal of Information Processing Systems), 2011, 7(2), 20, pp.271-286</ispartof><lds50>peer_reviewed</lds50><oa>free_for_read</oa><woscitedreferencessubscribed>false</woscitedreferencessubscribed></display><links><openurl>$$Topenurl_article</openurl><openurlfulltext>$$Topenurlfull_article</openurlfulltext><thumbnail>$$Tsyndetics_thumb_exl</thumbnail><link.rule.ids>314,780,784,27922,27923</link.rule.ids><backlink>$$Uhttps://www.kci.go.kr/kciportal/ci/sereArticleSearch/ciSereArtiView.kci?sereArticleSearchBean.artiId=ART001558969$$DAccess content in National Research Foundation of Korea (NRF)$$Hfree_for_read</backlink></links><search><creatorcontrib>Yamin Li</creatorcontrib><creatorcontrib>Shietung Peng</creatorcontrib><creatorcontrib>Wanming Chu</creatorcontrib><title>Parallel Prefix Computation and Sorting on a Recursive Dual-Net</title><title>Journal of information processing systems</title><description>In this paper, we propose efficient algorithms for parallel prefix computation and sorting on a recursive dual-net. The recursive dual-net RDN^k(B) for k &gt; 0 has (2n_o)^(2K)/2 nodes and d_0 + k links per node, where n_0 and d_0 are the number of nodes and the node-degree of the base-network B, respectively. Assume that each node holds one data item, the communication and computation time complexities of the algorithm for parallel prefix computation on RDN^k(B), k &gt; 0, are 2^(k+1)-2+2^kT_(comm)(0) and 2^(k+1)-2+2^kT_(comp)(0), respectively, where T_(comm)(0) and T_(comp)(0) are the communication and computation time complexities of the algorithm for parallel prefix computation on the base-network B, respectively. The algorithm for parallel sorting on RDN^k(B) is restricted on B = Q_m where Q_m is an m-cube. Assume that each node holds a single data item, the sorting algorithm runs in O((m2^k)^2) computation steps and O((km2^k)^2) communication steps, respectively. KCI Citation Count: 0</description><subject>컴퓨터학</subject><issn>1976-913X</issn><issn>2092-805X</issn><fulltext>true</fulltext><rsrctype>article</rsrctype><creationdate>2011</creationdate><recordtype>article</recordtype><recordid>eNotjF1LwzAYRoMoWKc_wLtcepOaN2mT5krG_KoMLduE3ZWXNBlxtZW0FX--8-PqPAceDiGXwFOps_z6qazWqeAAqU5FKjQckURwI1jB8-0xScBoxQzI7Sk5G4Y3zlWhTZaQmwojtq1raRWdD1900b9_TCOOoe8odg1d93EM3Y7-KF05O8UhfDp6O2HLnt14Tk48toO7-OeMvN7fbRaPbPnyUC7mS2YFlyMzUitQjnvlCrA8z2VmnC2Mw0YcFiopi0YJhxx8ptBYBIPaw-FsmlwJOSNXf90u-npvQ91j-OWur_exnq82ZS2EAgHyG1VbTIM</recordid><startdate>20110601</startdate><enddate>20110601</enddate><creator>Yamin Li</creator><creator>Shietung Peng</creator><creator>Wanming Chu</creator><general>한국정보처리학회</general><scope>ACYCR</scope></search><sort><creationdate>20110601</creationdate><title>Parallel Prefix Computation and Sorting on a Recursive Dual-Net</title><author>Yamin Li ; Shietung Peng ; Wanming Chu</author></sort><facets><frbrtype>5</frbrtype><frbrgroupid>cdi_FETCH-LOGICAL-c203t-937616e0f6e81c055349ec89ead249ea6338d62ea01f46a9ca19a7f181c9d5623</frbrgroupid><rsrctype>articles</rsrctype><prefilter>articles</prefilter><language>eng</language><creationdate>2011</creationdate><topic>컴퓨터학</topic><toplevel>peer_reviewed</toplevel><toplevel>online_resources</toplevel><creatorcontrib>Yamin Li</creatorcontrib><creatorcontrib>Shietung Peng</creatorcontrib><creatorcontrib>Wanming Chu</creatorcontrib><collection>Korean Citation Index</collection><jtitle>Journal of information processing systems</jtitle></facets><delivery><delcategory>Remote Search Resource</delcategory><fulltext>fulltext</fulltext></delivery><addata><au>Yamin Li</au><au>Shietung Peng</au><au>Wanming Chu</au><format>journal</format><genre>article</genre><ristype>JOUR</ristype><atitle>Parallel Prefix Computation and Sorting on a Recursive Dual-Net</atitle><jtitle>Journal of information processing systems</jtitle><date>2011-06-01</date><risdate>2011</risdate><spage>271</spage><epage>286</epage><pages>271-286</pages><issn>1976-913X</issn><eissn>2092-805X</eissn><abstract>In this paper, we propose efficient algorithms for parallel prefix computation and sorting on a recursive dual-net. The recursive dual-net RDN^k(B) for k &gt; 0 has (2n_o)^(2K)/2 nodes and d_0 + k links per node, where n_0 and d_0 are the number of nodes and the node-degree of the base-network B, respectively. Assume that each node holds one data item, the communication and computation time complexities of the algorithm for parallel prefix computation on RDN^k(B), k &gt; 0, are 2^(k+1)-2+2^kT_(comm)(0) and 2^(k+1)-2+2^kT_(comp)(0), respectively, where T_(comm)(0) and T_(comp)(0) are the communication and computation time complexities of the algorithm for parallel prefix computation on the base-network B, respectively. The algorithm for parallel sorting on RDN^k(B) is restricted on B = Q_m where Q_m is an m-cube. Assume that each node holds a single data item, the sorting algorithm runs in O((m2^k)^2) computation steps and O((km2^k)^2) communication steps, respectively. KCI Citation Count: 0</abstract><pub>한국정보처리학회</pub><doi>10.3745/JIPS.2011.7.2.271</doi><tpages>16</tpages><oa>free_for_read</oa></addata></record>
fulltext fulltext
identifier ISSN: 1976-913X
ispartof JIPS(Journal of Information Processing Systems), 2011, 7(2), 20, pp.271-286
issn 1976-913X
2092-805X
language eng
recordid cdi_nrf_kci_oai_kci_go_kr_ARTI_226121
source Free E-Journal (出版社公開部分のみ）
subjects 컴퓨터학
title Parallel Prefix Computation and Sorting on a Recursive Dual-Net
url http://sfxeu10.hosted.exlibrisgroup.com/loughborough?ctx_ver=Z39.88-2004&ctx_enc=info:ofi/enc:UTF-8&ctx_tim=2025-01-10T05%3A10%3A47IST&url_ver=Z39.88-2004&url_ctx_fmt=infofi/fmt:kev:mtx:ctx&rfr_id=info:sid/primo.exlibrisgroup.com:primo3-Article-nrf&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.genre=article&rft.atitle=Parallel%20Prefix%20Computation%20and%20Sorting%20on%20a%20Recursive%20Dual-Net&rft.jtitle=Journal%20of%20information%20processing%20systems&rft.au=Yamin%20Li&rft.date=2011-06-01&rft.spage=271&rft.epage=286&rft.pages=271-286&rft.issn=1976-913X&rft.eissn=2092-805X&rft_id=info:doi/10.3745/JIPS.2011.7.2.271&rft_dat=%3Cnrf%3Eoai_kci_go_kr_ARTI_226121%3C/nrf%3E%3Cgrp_id%3Ecdi_FETCH-LOGICAL-c203t-937616e0f6e81c055349ec89ead249ea6338d62ea01f46a9ca19a7f181c9d5623%3C/grp_id%3E%3Coa%3E%3C/oa%3E%3Curl%3E%3C/url%3E&rft_id=info:oai/&rft_id=info:pmid/&rfr_iscdi=true