Menu
×
John L. Dart Library
9 a.m. – 7 p.m.
Phone: (843) 722-7550
West Ashley Library
9 a.m. – 7 p.m.
Phone: (843) 766-6635
Folly Beach Library
9 a.m. - 5:30 p.m.
Phone: (843) 588-2001
Edgar Allan Poe/Sullivan's Island Library
Closed for renovations
Phone: (843) 883-3914
Wando Mount Pleasant Library
9 a.m. – 8 p.m.
Phone: (843) 805-6888
Village Library
9 a.m. - 6 p.m.
Phone: (843) 884-9741
St. Paul's/Hollywood Library
9 a.m. – 8 p.m.
Phone: (843) 889-3300
Otranto Road Library
9 a.m. – 8 p.m.
Phone: (843) 572-4094
Mt. Pleasant Library
9 a.m. – 8 p.m.
Phone: (843) 849-6161
McClellanville Library
9 a.m. - 6 p.m.
Phone: (843) 887-3699
Keith Summey North Charleston Library
9 a.m. – 8 p.m.
Phone: (843) 744-2489
John's Island Library
9 a.m. – 8 p.m.
Phone: (843) 559-1945
Hurd/St. Andrews Library
9 a.m. – 8 p.m.
Phone: (843) 766-2546
Miss Jane's Building (Edisto Library Temporary Location)
9 a.m. - 4 p.m.
Phone: (843) 869-2355
Dorchester Road Library
9 a.m. – 8 p.m.
Phone: (843) 552-6466
Baxter-Patrick James Island
9 a.m. – 8 p.m.
Phone: (843) 795-6679
Main Library
9 a.m. – 8 p.m.
Phone: (843) 805-6930
Bees Ferry West Ashley Library
9 a.m. – 8 p.m.
Phone: (843) 805-6892
Mobile Library
9 a.m. - 5 p.m.
Phone: (843) 805-6909
Today's Hours
John L. Dart Library
9 a.m. – 7 p.m.
Phone: (843) 722-7550
West Ashley Library
9 a.m. – 7 p.m.
Phone: (843) 766-6635
Folly Beach Library
9 a.m. - 5:30 p.m.
Phone: (843) 588-2001
Edgar Allan Poe/Sullivan's Island Library
Closed for renovations
Phone: (843) 883-3914
Wando Mount Pleasant Library
9 a.m. – 8 p.m.
Phone: (843) 805-6888
Village Library
9 a.m. - 6 p.m.
Phone: (843) 884-9741
St. Paul's/Hollywood Library
9 a.m. – 8 p.m.
Phone: (843) 889-3300
Otranto Road Library
9 a.m. – 8 p.m.
Phone: (843) 572-4094
Mt. Pleasant Library
9 a.m. – 8 p.m.
Phone: (843) 849-6161
McClellanville Library
9 a.m. - 6 p.m.
Phone: (843) 887-3699
Keith Summey North Charleston Library
9 a.m. – 8 p.m.
Phone: (843) 744-2489
John's Island Library
9 a.m. – 8 p.m.
Phone: (843) 559-1945
Hurd/St. Andrews Library
9 a.m. – 8 p.m.
Phone: (843) 766-2546
Miss Jane's Building (Edisto Library Temporary Location)
9 a.m. - 4 p.m.
Phone: (843) 869-2355
Dorchester Road Library
9 a.m. – 8 p.m.
Phone: (843) 552-6466
Baxter-Patrick James Island
9 a.m. – 8 p.m.
Phone: (843) 795-6679
Main Library
9 a.m. – 8 p.m.
Phone: (843) 805-6930
Bees Ferry West Ashley Library
9 a.m. – 8 p.m.
Phone: (843) 805-6892
Mobile Library
9 a.m. - 5 p.m.
Phone: (843) 805-6909
Patron Login
menu
Item request has been placed!
×
Item request cannot be made.
×
Processing Request
Trade-offs between Communication Throughput and Parallel Time
Item request has been placed!
×
Item request cannot be made.
×
Processing Request
- Author(s): Mansour, Yishay; Nisan, Noam; Vishkin, Uzi
- Source:
Journal of Complexity; March 1999, Vol. 15 Issue: 1 p148-166, 19p - Source:
- Additional Information
- Abstract: We study the effect of limited communication throughput on parallel computation in a setting where the number of processors is much smaller than the length of the input. Our model haspprocessors that communicate through a shared memory of sizem. The input has sizenand can be read directly by all the processors. We will be primarily interested in studying cases wheren⪢p⪢m. As a test case we study the list reversal problem. For this problem we prove a time lower bound ofΩ(n/mp). (A similar lower bound holds also for the problems of sorting, finding all unique elements, convolution, and universal hashing.) This result demonstrates that limiting the communication (i.e., smallm) could have significant effect on parallel computation. We show an almost matching upper bound ofO((n/mp)logO(1)n). The upper bound requires the development of a few interesting techniques which can alleviate the limited communication in some general settings. Specifically, we show how to emulate a large shared memory on a limited shared memory efficiently. The lower bound applies even to randomized machines, and the upper bound is a randomized algorithm. We also argue that some standard methodology for designing parallel algorithms appears to require a relatively high level of communication throughput. Our results suggest that new alternative methodologies that need a lower such level must be invented for parallel machines that enable a low level of communication throughput, since otherwise those machines will be severly handicapped as general purpose parallel machines. Although we do not rule that out, we cannot offer any encouraging evidence to suggest that such new methodologies are likely to be found.
- Abstract:
Contact CCPL
Copyright 2022 Charleston County Public Library Powered By EBSCO Stacks 3.3.0 [350.3] | Staff Login
No Comments.