The complexity of parallel prefix problems on small domains

The authors study the complexity of some prefix problems in the CRCW PRAM model. The main result is an Omega ( alpha (n)) lower bound for chaining, matching a previous upper bound and solving an open problem. They give reductions to show an Omega ( alpha (n)) lower bound on the complexity of the pre...

Full description

Saved in:
Bibliographic Details
Main Authors: Chaudhuri, S., Radhakrishnan, J.
Format: Conference Proceeding
Language:English
Subjects:
Computer science
Concurrent computing
Joining processes
Law
Legal factors
Parallel algorithms
Phase change random access memory
Upper bound
Online Access:Request full text
Tags: Add Tag
No Tags, Be the first to tag this record!
cited_by
cites
container_end_page 647
container_issue
container_start_page 638
container_title
container_volume
creator Chaudhuri, S.
Radhakrishnan, J.
description The authors study the complexity of some prefix problems in the CRCW PRAM model. The main result is an Omega ( alpha (n)) lower bound for chaining, matching a previous upper bound and solving an open problem. They give reductions to show an Omega ( alpha (n)) lower bound on the complexity of the prefix maxima and range maxima problems even when the domain is (1,...,n). An interesting consequence is that prefix maximum is strictly harder than simple maximum. They also give a reduction to show an Omega ( alpha (n)) lower bound on a parenthesis matching problem, matching the upper bound. No lower bounds were previously known for any of these problems. The lower bounds contribute to the study of very fast parallel algorithms by introducing techniques for proving lower bounds for small domain problems.< >
doi_str_mv 10.1109/SFCS.1992.267787
format conference_proceeding
fullrecord <record><control><sourceid>ieee_6IE</sourceid><recordid>TN_cdi_ieee_primary_267787</recordid><sourceformat>XML</sourceformat><sourcesystem>PC</sourcesystem><ieee_id>267787</ieee_id><sourcerecordid>267787</sourcerecordid><originalsourceid>FETCH-LOGICAL-i214t-3e9e913bbdc6f83f05b1823bcc85451eb693fa71982a8c7f2ea48dd60b90a10a3</originalsourceid><addsrcrecordid>eNotj0FLwzAYhgMiTOfuw1P-QGu-pEkTPElxThh42DyPJP2CkWQtzQ7bv7cwn8tzeOCFl5A1sBqAmZf9ptvXYAyvuWpb3d6RR6ZBK24Y4wuyKuWXzUipBZcP5PXwg9QPeUx4iecrHQId7WRTwkTHCUO8zBpcwlzocKIlz4n2Q7bxVJ7IfbCp4OrfS_K9eT9022r39fHZve2qyKE5VwINGhDO9V4FLQKTDjQXznstGwnolBHBtmA0t9q3gaNtdN8r5gyzwKxYkufbbkTE4zjFbKfr8XZP_AEN9kX-</addsrcrecordid><sourcetype>Publisher</sourcetype><iscdi>true</iscdi><recordtype>conference_proceeding</recordtype></control><display><type>conference_proceeding</type><title>The complexity of parallel prefix problems on small domains</title><source>IEEE Electronic Library (IEL) Conference Proceedings</source><creator>Chaudhuri, S. ; Radhakrishnan, J.</creator><creatorcontrib>Chaudhuri, S. ; Radhakrishnan, J.</creatorcontrib><description>The authors study the complexity of some prefix problems in the CRCW PRAM model. The main result is an Omega ( alpha (n)) lower bound for chaining, matching a previous upper bound and solving an open problem. They give reductions to show an Omega ( alpha (n)) lower bound on the complexity of the prefix maxima and range maxima problems even when the domain is (1,...,n). An interesting consequence is that prefix maximum is strictly harder than simple maximum. They also give a reduction to show an Omega ( alpha (n)) lower bound on a parenthesis matching problem, matching the upper bound. No lower bounds were previously known for any of these problems. The lower bounds contribute to the study of very fast parallel algorithms by introducing techniques for proving lower bounds for small domain problems.&lt; &gt;</description><identifier>ISBN: 0818629002</identifier><identifier>ISBN: 9780818629006</identifier><identifier>DOI: 10.1109/SFCS.1992.267787</identifier><language>eng</language><publisher>IEEE Comput. Soc. Press</publisher><subject>Computer science ; Concurrent computing ; Joining processes ; Law ; Legal factors ; Parallel algorithms ; Phase change random access memory ; Upper bound</subject><ispartof>Proceedings., 33rd Annual Symposium on Foundations of Computer Science, 1992, p.638-647</ispartof><oa>free_for_read</oa><woscitedreferencessubscribed>false</woscitedreferencessubscribed></display><links><openurl>$$Topenurl_article</openurl><openurlfulltext>$$Topenurlfull_article</openurlfulltext><thumbnail>$$Tsyndetics_thumb_exl</thumbnail><linktohtml>$$Uhttps://ieeexplore.ieee.org/document/267787$$EHTML$$P50$$Gieee$$H</linktohtml><link.rule.ids>309,310,780,784,789,790,2058,4050,4051,27925,54920</link.rule.ids><linktorsrc>$$Uhttps://ieeexplore.ieee.org/document/267787$$EView_record_in_IEEE$$FView_record_in_$$GIEEE</linktorsrc></links><search><creatorcontrib>Chaudhuri, S.</creatorcontrib><creatorcontrib>Radhakrishnan, J.</creatorcontrib><title>The complexity of parallel prefix problems on small domains</title><title>Proceedings., 33rd Annual Symposium on Foundations of Computer Science</title><addtitle>SFCS</addtitle><description>The authors study the complexity of some prefix problems in the CRCW PRAM model. The main result is an Omega ( alpha (n)) lower bound for chaining, matching a previous upper bound and solving an open problem. They give reductions to show an Omega ( alpha (n)) lower bound on the complexity of the prefix maxima and range maxima problems even when the domain is (1,...,n). An interesting consequence is that prefix maximum is strictly harder than simple maximum. They also give a reduction to show an Omega ( alpha (n)) lower bound on a parenthesis matching problem, matching the upper bound. No lower bounds were previously known for any of these problems. The lower bounds contribute to the study of very fast parallel algorithms by introducing techniques for proving lower bounds for small domain problems.&lt; &gt;</description><subject>Computer science</subject><subject>Concurrent computing</subject><subject>Joining processes</subject><subject>Law</subject><subject>Legal factors</subject><subject>Parallel algorithms</subject><subject>Phase change random access memory</subject><subject>Upper bound</subject><isbn>0818629002</isbn><isbn>9780818629006</isbn><fulltext>true</fulltext><rsrctype>conference_proceeding</rsrctype><creationdate>1992</creationdate><recordtype>conference_proceeding</recordtype><sourceid>6IE</sourceid><recordid>eNotj0FLwzAYhgMiTOfuw1P-QGu-pEkTPElxThh42DyPJP2CkWQtzQ7bv7cwn8tzeOCFl5A1sBqAmZf9ptvXYAyvuWpb3d6RR6ZBK24Y4wuyKuWXzUipBZcP5PXwg9QPeUx4iecrHQId7WRTwkTHCUO8zBpcwlzocKIlz4n2Q7bxVJ7IfbCp4OrfS_K9eT9022r39fHZve2qyKE5VwINGhDO9V4FLQKTDjQXznstGwnolBHBtmA0t9q3gaNtdN8r5gyzwKxYkufbbkTE4zjFbKfr8XZP_AEN9kX-</recordid><startdate>1992</startdate><enddate>1992</enddate><creator>Chaudhuri, S.</creator><creator>Radhakrishnan, J.</creator><general>IEEE Comput. Soc. Press</general><scope>6IE</scope><scope>6IL</scope><scope>CBEJK</scope><scope>RIE</scope><scope>RIL</scope></search><sort><creationdate>1992</creationdate><title>The complexity of parallel prefix problems on small domains</title><author>Chaudhuri, S. ; Radhakrishnan, J.</author></sort><facets><frbrtype>5</frbrtype><frbrgroupid>cdi_FETCH-LOGICAL-i214t-3e9e913bbdc6f83f05b1823bcc85451eb693fa71982a8c7f2ea48dd60b90a10a3</frbrgroupid><rsrctype>conference_proceedings</rsrctype><prefilter>conference_proceedings</prefilter><language>eng</language><creationdate>1992</creationdate><topic>Computer science</topic><topic>Concurrent computing</topic><topic>Joining processes</topic><topic>Law</topic><topic>Legal factors</topic><topic>Parallel algorithms</topic><topic>Phase change random access memory</topic><topic>Upper bound</topic><toplevel>online_resources</toplevel><creatorcontrib>Chaudhuri, S.</creatorcontrib><creatorcontrib>Radhakrishnan, J.</creatorcontrib><collection>IEEE Electronic Library (IEL) Conference Proceedings</collection><collection>IEEE Proceedings Order Plan All Online (POP All Online) 1998-present by volume</collection><collection>IEEE Xplore All Conference Proceedings</collection><collection>IEEE/IET Electronic Library (IEL)</collection><collection>IEEE Proceedings Order Plans (POP All) 1998-Present</collection></facets><delivery><delcategory>Remote Search Resource</delcategory><fulltext>fulltext_linktorsrc</fulltext></delivery><addata><au>Chaudhuri, S.</au><au>Radhakrishnan, J.</au><format>book</format><genre>proceeding</genre><ristype>CONF</ristype><atitle>The complexity of parallel prefix problems on small domains</atitle><btitle>Proceedings., 33rd Annual Symposium on Foundations of Computer Science</btitle><stitle>SFCS</stitle><date>1992</date><risdate>1992</risdate><spage>638</spage><epage>647</epage><pages>638-647</pages><isbn>0818629002</isbn><isbn>9780818629006</isbn><abstract>The authors study the complexity of some prefix problems in the CRCW PRAM model. The main result is an Omega ( alpha (n)) lower bound for chaining, matching a previous upper bound and solving an open problem. They give reductions to show an Omega ( alpha (n)) lower bound on the complexity of the prefix maxima and range maxima problems even when the domain is (1,...,n). An interesting consequence is that prefix maximum is strictly harder than simple maximum. They also give a reduction to show an Omega ( alpha (n)) lower bound on a parenthesis matching problem, matching the upper bound. No lower bounds were previously known for any of these problems. The lower bounds contribute to the study of very fast parallel algorithms by introducing techniques for proving lower bounds for small domain problems.&lt; &gt;</abstract><pub>IEEE Comput. Soc. Press</pub><doi>10.1109/SFCS.1992.267787</doi><tpages>10</tpages><oa>free_for_read</oa></addata></record>
fulltext fulltext_linktorsrc
identifier ISBN: 0818629002
ispartof Proceedings., 33rd Annual Symposium on Foundations of Computer Science, 1992, p.638-647
issn
language eng
recordid cdi_ieee_primary_267787
source IEEE Electronic Library (IEL) Conference Proceedings
subjects Computer science
Concurrent computing
Joining processes
Law
Legal factors
Parallel algorithms
Phase change random access memory
Upper bound
title The complexity of parallel prefix problems on small domains
url http://sfxeu10.hosted.exlibrisgroup.com/loughborough?ctx_ver=Z39.88-2004&ctx_enc=info:ofi/enc:UTF-8&ctx_tim=2025-01-07T18%3A09%3A31IST&url_ver=Z39.88-2004&url_ctx_fmt=infofi/fmt:kev:mtx:ctx&rfr_id=info:sid/primo.exlibrisgroup.com:primo3-Article-ieee_6IE&rft_val_fmt=info:ofi/fmt:kev:mtx:book&rft.genre=proceeding&rft.atitle=The%20complexity%20of%20parallel%20prefix%20problems%20on%20small%20domains&rft.btitle=Proceedings.,%2033rd%20Annual%20Symposium%20on%20Foundations%20of%20Computer%20Science&rft.au=Chaudhuri,%20S.&rft.date=1992&rft.spage=638&rft.epage=647&rft.pages=638-647&rft.isbn=0818629002&rft.isbn_list=9780818629006&rft_id=info:doi/10.1109/SFCS.1992.267787&rft_dat=%3Cieee_6IE%3E267787%3C/ieee_6IE%3E%3Cgrp_id%3Ecdi_FETCH-LOGICAL-i214t-3e9e913bbdc6f83f05b1823bcc85451eb693fa71982a8c7f2ea48dd60b90a10a3%3C/grp_id%3E%3Coa%3E%3C/oa%3E%3Curl%3E%3C/url%3E&rft_id=info:oai/&rft_id=info:pmid/&rft_ieee_id=267787&rfr_iscdi=true