http://hdl.handle.net/1903/1658 2013-05-19T20:50:49Z 2013-05-19T20:50:49Z Edwards, James A. Vishkin, Uzi http://hdl.handle.net/1903/13890 2013-05-04T02:32:43Z 2013-04-20T00:00:00Z

Title: Empirical Speedup Study of Truly Parallel Data Compression Authors: Edwards, James A.; Vishkin, Uzi Abstract: We present an empirical study of novel work-optimal parallel algorithms for Burrows-Wheeler compression and decompression of strings over a constant alphabet. To validate these theoretical algorithms, we implement them on the experimental XMT computing platform developed especially for supporting parallel algorithms at the University of Maryland. We show speedups of up to 25x for compression, and 13x for decompression, versus bzip2, the de facto standard implementation of Burrows-Wheeler compression. Unlike existing approaches, which assign an entire (e.g., 900KB) block to a processor that processes the block serially, our approach is “truly parallel” as it processes in parallel the entire input. Besides the theoretical interest in solving the “right” problem, the importance of data compression speed for small inputs even at great expense of quality (compressed size of data) is demonstrated by the introduction of Google’s Snappy for MapReduce. Perhaps surprisingly, we show feasibility of holding on to quality, while even beating Snappy on speed. In turn, this work adds new evidence in support of the XMT/PRAM thesis: that an XMT-like many-core hardware/ software platform may be necessary for enabling general-purpose parallel computing. Comparison of our results to recently published work suggests 70x improvement over what current commercial parallel hardware can achieve.

2013-04-20T00:00:00Z Elson, Edward C http://hdl.handle.net/1903/13369 2013-01-11T03:51:35Z 2010-06-24T00:00:00Z

Title: Complex life forms may arise from electrical processes Authors: Elson, Edward C Abstract: There is still not an appealing and testable model to explain how single-celled organisms, usually following fusion of male and female gametes, proceed to grow and evolve into multi-cellular, complexly differentiated systems, a particular species following virtually an invariant and unique growth pattern. An intrinsic electrical oscillator, resembling the cardiac pacemaker, may explain the process. Highly auto-correlated, it could live independently of ordinary thermodynamic processes which mandate increasing disorder, and could coordinate growth and differentiation of organ anlage.

2010-06-24T00:00:00Z Borah, Deva K Boucouvalas, Anthony C Davis, Christopher C Hranilovic, Steve Yiannopoulos, Konstantinos http://hdl.handle.net/1903/13347 2013-01-11T03:53:38Z 2012-03-07T00:00:00Z

Title: A review of communication-oriented optical wireless systems Authors: Borah, Deva K; Boucouvalas, Anthony C; Davis, Christopher C; Hranilovic, Steve; Yiannopoulos, Konstantinos Abstract: This article presents an overview of optical wireless (OW) communication systems that operate both in the short- (personal and indoor systems) and the long-range (outdoor and hybrid) regimes. Each of these areas is discussed in terms of (a) key requirements, (b) their application framework, (c) major impairments and applicable mitigation techniques, and (d) current and/or future trends. Personal communication systems are discussed within the context of point-to-point ultra-high speed data transfer. The most relevant application framework and related standards are presented, including the next generation Giga-IR standard that extends personal communication speeds to over 1 Gb/s. As far as indoor systems are concerned, emphasis is given on modeling the dispersive nature of indoor OW channels, on the limitations that dispersion imposes on user mobility and dispersion mitigation techniques. Visible light communication systems, which provide both illumination and communication over visible or hybrid visible/ infrared LEDs, are presented as the most important representative of future indoor OW systems. The discussion on outdoor systems focuses on the impact of atmospheric effects on the optical channel and associated mitigation techniques that extend the realizable link lengths and transfer rates. Currently, outdoor OW is commercially available at 10 Gb/s Ethernet speeds for Metro networks and Local-Area-Network interconnections and speeds are expected to increase as faster and more reliable optical components become available. This article concludes with hybrid optical wireless/radio-frequency (OW/RF) systems that employ an additional RF link to improve the overall system reliability. Emphasis is given on cooperation techniques between the reliable RF subsystem and the broadband OW system.

2012-03-07T00:00:00Z Edwards, James A. Vishkin, Uzi http://hdl.handle.net/1903/13299 2012-11-14T03:31:24Z 2012-11-12T00:00:00Z

Title: Parallel Algorithms for Burrows-Wheeler Compression and Decompression Authors: Edwards, James A.; Vishkin, Uzi Abstract: We present work-optimal PRAM algorithms for Burrows-Wheeler compression and decompression of strings over a constant alphabet. For a string of length n, the depth of the compression algorithm is O(log2 n), and the depth of the the corresponding decompression algorithm is O(log n). These appear to be the first polylogarithmic-time work-optimal parallel algorithms for any standard lossless compression scheme. The algorithms for the individual stages of compression and decompression may also be of independent interest: 1. a novel O(log n)-time, O(n)-work PRAM algorithm for Huffman decoding; 2. original insights into the stages of the BW compression and decompression problems, bringing out parallelism that was not readily apparent, allowing them to be mapped to elementary parallel routines that have O(log n)-time, O(n)-work solutions, such as: (i) prefix-sums problems with an appropriately-defined associative binary operator for several stages, and (ii) list ranking for the final stage of decompression.

2012-11-12T00:00:00Z