Automatically assigned DDC number: 00435
Manually assigned DDC number: 00435

Number of references: 4

Title: New Coding Techniques for Improved Bandwidth Utilization

Author:

Subject: Micah Adler New Coding Techniques for Improved Bandwidth Utilization

Description: this paper, we introduce a new coding technique for transmitting the XOR of carefully selected patterns of bits to be communicated which greatly reduces bandwidth requirements in some settings. This technique has broader applications. For example, we demonstrate that the coding technique has a surprising application to a simple I/O (Input / Output) complexity problem related to finding the transpose of a matrix. Our main results are developed in the PRAM(m) model, a limited bandwidth PRAM model where p processors communicate through a small globally shared memory of m bits. We provide new algorithms for the problems of sorting and permutation routing. For the concurrent read PRAM(m), as p grows with m

Contributor: The Pennsylvania State University CiteSeer Archives

Publisher: unknown

Date: 1998-01-29

Pubyear: 1998

Format: ps

Identifier: http://citeseer.ist.psu.edu/148778.html

Source: http://www.cs.toronto.edu/~micah/pubs/coding.ps

Language: en

Relation:

Relation:

Relation:

Relation:

Rights: unrestricted

Graph

<?xml version="1.0" encoding="UTF-8"?>

<references_metadata>

<rec ID="/31084.html" Type="inproceedings" CiteSeer_Book="Principles Practice of Parallel Programming" CiteSeer_Volume="" Title="{LogP}: Towards a Realistic Model of Parallel Computation,">

<identifier Org="ISBN:0070730202" Paper_ID="/31084.html" Extracted="0070730202" DDC="004/.35" Normalized_DDC="00435" Normalized_Weight="0.05555555555555555" />

<identifier Org="ISBN:0387986642" Paper_ID="/31084.html" Extracted="0387986642" DDC="004/.35" Normalized_DDC="00435" Normalized_Weight="0.05555555555555555" />

<identifier Org="ISBN:0387986804" Paper_ID="/31084.html" Extracted="0387986804" DDC="004/.35" Normalized_DDC="00435" Normalized_Weight="0.05555555555555555" />

<identifier Org="ISBN:084932615X" Paper_ID="/31084.html" Extracted="084932615X" DDC="004/.35" Normalized_DDC="00435" Normalized_Weight="0.05555555555555555" />

<identifier Org="ISBN:0897915895" Paper_ID="/31084.html" Extracted="0897915895" DDC="005.2" Normalized_DDC="0052" Normalized_Weight="0.05555555555555555" />

<identifier Org="ISBN:1584886234" Paper_ID="/31084.html" Extracted="1584886234" DDC="005.1" Normalized_DDC="0051" Normalized_Weight="0.05555555555555555" />

<identifier Org="ISBN:354040788X" Paper_ID="/31084.html" Extracted="354040788X" DDC="004/.35" Normalized_DDC="00435" Normalized_Weight="0.05555555555555555" />

<identifier Org="ISBN:3540424954" Paper_ID="/31084.html" Extracted="3540424954" DDC="004/.35" Normalized_DDC="00435" Normalized_Weight="0.05555555555555555" />

<identifier Org="ISBN:3540428623" Paper_ID="/31084.html" Extracted="3540428623" DDC="005.453" Normalized_DDC="005453" Normalized_Weight="0.05555555555555555" />

<identifier Org="ISBN:3540437924" Paper_ID="/31084.html" Extracted="3540437924" DDC="004/.35" Normalized_DDC="00435" Normalized_Weight="0.05555555555555555" />

<identifier Org="ISBN:3540616268" Paper_ID="/31084.html" Extracted="3540616268" DDC="004/.35" Normalized_DDC="00435" Normalized_Weight="0.05555555555555555" />

<identifier Org="ISBN:3540620486" Paper_ID="/31084.html" Extracted="3540620486" DDC="001.64" Normalized_DDC="00164" Normalized_Weight="0.05555555555555555" />

<identifier Org="ISBN:3540638768" Paper_ID="/31084.html" Extracted="3540638768" DDC="001.64" Normalized_DDC="00164" Normalized_Weight="0.05555555555555555" />

<identifier Org="ISBN:3540649522" Paper_ID="/31084.html" Extracted="3540649522" DDC="004/.35" Normalized_DDC="00435" Normalized_Weight="0.05555555555555555" />

<identifier Org="ISBN:3540658319" Paper_ID="/31084.html" Extracted="3540658319" DDC="004/.35" Normalized_DDC="00435" Normalized_Weight="0.05555555555555555" />

<identifier Org="ISBN:3540754431" Paper_ID="/31084.html" Extracted="3540754431" DDC="004" Normalized_DDC="004" Normalized_Weight="0.05555555555555555" />

<identifier Org="ISBN:3540775595" Paper_ID="/31084.html" Extracted="3540775595" DDC="004.2/2" Normalized_DDC="00422" Normalized_Weight="0.05555555555555555" />

<identifier Org="ISBN:3540874747" Paper_ID="/31084.html" Extracted="3540874747" />

<identifier Org="ISBN:905199267X" Paper_ID="/31084.html" Extracted="905199267X" DDC="004/.35" Normalized_DDC="00435" Normalized_Weight="0.05555555555555555" />

</rec>

<rec ID="/102758.html" Type="inproceedings" CiteSeer_Book="IEEE Symposium on Foundations of Computer Science" CiteSeer_Volume="" Title="Efficient Out-of-Core Algorithms for Linear Relaxation Using Blocking Covers (Extended Abstract),">

<identifier Org="ISBN:0818643706" Paper_ID="/102758.html" Extracted="0818643706" DDC="004" Normalized_DDC="004" Normalized_Weight="1.0" />

</rec>

<rec ID="/174559.html" Type="inproceedings" CiteSeer_Book="" CiteSeer_Volume="" Title="Trade-offs between communication throughput and parallel time,">

<identifier Org="ISBN:0387986804" Paper_ID="/174559.html" Extracted="0387986804" DDC="004/.35" Normalized_DDC="00435" Normalized_Weight="0.16666666666666666" />

<identifier Org="ISBN:078033762X" Paper_ID="/174559.html" Extracted="078033762X" />

<identifier Org="ISBN:0818664274" Paper_ID="/174559.html" Extracted="0818664274" DDC="004.35" Normalized_DDC="00435" Normalized_Weight="0.16666666666666666" />

<identifier Org="ISBN:0897916638" Paper_ID="/174559.html" Extracted="0897916638" DDC="004.01" Normalized_DDC="00401" Normalized_Weight="0.16666666666666666" />

<identifier Org="ISBN:0897917170" Paper_ID="/174559.html" Extracted="0897917170" DDC="004.22" Normalized_DDC="00422" Normalized_Weight="0.16666666666666666" />

<identifier Org="ISBN:0897918908" Paper_ID="/174559.html" Extracted="0897918908" />

<identifier Org="ISBN:1581131240" Paper_ID="/174559.html" Extracted="1581131240" />

<identifier Org="ISBN:1581131844" Paper_ID="/174559.html" Extracted="1581131844" />

<identifier Org="ISBN:3540422331" Paper_ID="/174559.html" Extracted="3540422331" DDC="004" Normalized_DDC="004" Normalized_Weight="0.16666666666666666" />

<identifier Org="ISBN:3540642757" Paper_ID="/174559.html" Extracted="3540642757" DDC="004" Normalized_DDC="004" Normalized_Weight="0.16666666666666666" />

</rec>

<rec ID="/195438.html" Type="techreport" CiteSeer_Book="" CiteSeer_Volume="" Title="Algorithms for Parallel Memory {I}: Two-Level Memories,">

<identifier Org="ISBN:0387301623" Paper_ID="/195438.html" Extracted="0387301623" DDC="518.103" Normalized_DDC="518103" Normalized_Weight="0.07142857142857142" />

<identifier Org="ISBN:0769501435" Paper_ID="/195438.html" Extracted="0769501435" />

<identifier Org="ISBN:0821811843" Paper_ID="/195438.html" Extracted="0821811843" DDC="005.4/2" Normalized_DDC="00542" Normalized_Weight="0.07142857142857142" />

<identifier Org="ISBN:0849308852" Paper_ID="/195438.html" Extracted="0849308852" DDC="004" Normalized_DDC="004" Normalized_Weight="0.07142857142857142" />

<identifier Org="ISBN:0897915992" Paper_ID="/195438.html" Extracted="0897915992" />

<identifier Org="ISBN:0898714907" Paper_ID="/195438.html" Extracted="0898714907" />

<identifier Org="ISBN:0898716055" Paper_ID="/195438.html" Extracted="0898716055" />

<identifier Org="ISBN:1558606645" Paper_ID="/195438.html" Extracted="1558606645" DDC="004/.3" Normalized_DDC="0043" Normalized_Weight="0.07142857142857142" />

<identifier Org="ISBN:3540211993" Paper_ID="/195438.html" Extracted="3540211993" DDC="005.275" Normalized_DDC="005275" Normalized_Weight="0.07142857142857142" />

<identifier Org="ISBN:3540223398" Paper_ID="/195438.html" Extracted="3540223398" DDC="518/.1" Normalized_DDC="5181" Normalized_Weight="0.07142857142857142" />

<identifier Org="ISBN:3540309357" Paper_ID="/195438.html" Extracted="3540309357" DDC="004.015118" Normalized_DDC="004015118" Normalized_Weight="0.07142857142857142" />

<identifier Org="ISBN:354041004X" Paper_ID="/195438.html" Extracted="354041004X" DDC="004/.01/5118" Normalized_DDC="004015118" Normalized_Weight="0.07142857142857142" />

<identifier Org="ISBN:3540424938" Paper_ID="/195438.html" Extracted="3540424938" DDC="005.1" Normalized_DDC="0051" Normalized_Weight="0.07142857142857142" />

<identifier Org="ISBN:3540441808" Paper_ID="/195438.html" Extracted="3540441808" DDC="005.1" Normalized_DDC="0051" Normalized_Weight="0.07142857142857142" />

<identifier Org="ISBN:3540603131" Paper_ID="/195438.html" Extracted="3540603131" DDC="004/.01/5118" Normalized_DDC="004015118" Normalized_Weight="0.07142857142857142" />

<identifier Org="ISBN:3540605738" Paper_ID="/195438.html" Extracted="3540605738" DDC="005.1" Normalized_DDC="0051" Normalized_Weight="0.07142857142857142" />

<identifier Org="ISBN:3540662006" Paper_ID="/195438.html" Extracted="3540662006" DDC="004" Normalized_DDC="004" Normalized_Weight="0.07142857142857142" />

<identifier Org="ISBN:3540772197" Paper_ID="/195438.html" Extracted="3540772197" />

<identifier Org="ISBN:3540787909" Paper_ID="/195438.html" Extracted="3540787909" DDC="005.4/53" Normalized_DDC="005453" Normalized_Weight="0.07142857142857142" />

</rec>

<rec ID="SELF" Type="SELF" CiteSeer_Book="SELF" CiteSeer_Volume="SELF" Title="New Coding Techniques for Improved Bandwidth Utilization">

<identifier Org="ISBN:078033762X" Paper_ID="SELF" Extracted="078033762X" />

<identifier Org="ISBN:0818681322" Paper_ID="SELF" Extracted="0818681322" DDC="003/.54" Normalized_DDC="00354" Normalized_Weight="0.25" />

<identifier Org="ISBN:0821811843" Paper_ID="SELF" Extracted="0821811843" DDC="005.4/2" Normalized_DDC="00542" Normalized_Weight="0.25" />

<identifier Org="ISBN:0897918886" Paper_ID="SELF" Extracted="0897918886" />

<identifier Org="ISBN:0897918908" Paper_ID="SELF" Extracted="0897918908" />

<identifier Org="ISBN:0897919963" Paper_ID="SELF" Extracted="0897919963" />

<identifier Org="ISBN:1402004893" Paper_ID="SELF" Extracted="1402004893" DDC="005.75/8" Normalized_DDC="005758" Normalized_Weight="0.25" />

<identifier Org="ISBN:1581131240" Paper_ID="SELF" Extracted="1581131240" />

<identifier Org="ISBN:1581131844" Paper_ID="SELF" Extracted="1581131844" />

<identifier Org="ISBN:1601981066" Paper_ID="SELF" Extracted="1601981066" />

<identifier Org="ISBN:3540676902" Paper_ID="SELF" Extracted="3540676902" DDC="511.8" Normalized_DDC="5118" Normalized_Weight="0.25" />

</rec>

</references_metadata>