http://hdl.handle.net/1903/12 2013-06-19T14:44:13Z 2013-06-19T14:44:13Z Jeon, Jinseong Micinski, Kristopher K. Foster, Jeffrey S. http://hdl.handle.net/1903/13946 2013-06-16T02:35:31Z 2012-07-31T00:00:00Z

Title: SymDroid: Symbolic Execution for Dalvik Bytecode Authors: Jeon, Jinseong; Micinski, Kristopher K.; Foster, Jeffrey S. Abstract: Apps on Google's Android mobile device platform are written in Java, but are compiled to a special bytecode language called Dalvik. In this paper, we introduce SymDroid, a symbolic executor that operates directly on Dalvik bytecode. SymDroid begins by first translating Dalvik into mu-Dalvik, a simpler language that has only 16 instructions, in contrast to Dalvik's more than 200 instructions. We present a formalism for SymDroid's symbolic executor, which can be described with a small number of operational semantics rules; this semantics may be of independent interest. In addition to modeling bytecode instructions, SymDroid also contains models of some key portions of the Android platform, including libraries and the platform's lifecycle control code. We evaluated SymDroid in two ways. First, we ran it on the Android Compatibility Test Suite, and found it passed all tests except ones that used library or system routines we have not yet implemented. On this test suite, SymDroid runs about twice as slow as the Dalvik VM, and about twice as fast as the Java VM. Second, we used SymDroid to discover the (path) conditions under which contacts may be accessed on an Android app, and found it was able to do so successfully. These results suggest that SymDroid, while still a prototype, is a promising first step in enabling direct, precise analysis of Android apps.

2012-07-31T00:00:00Z Berlin, Konstantin Gumerov, Nail A. Fushman, David Duraiswami, Ramani http://hdl.handle.net/1903/13941 2013-06-08T02:31:23Z 2013-05-25T00:00:00Z

Title: Hierarchical O(N) Computation of Small-Angle Scattering Profiles and their Associated Derivatives Authors: Berlin, Konstantin; Gumerov, Nail A.; Fushman, David; Duraiswami, Ramani Abstract: Fast algorithms for Debye summation, which arises in computations performed in crystallography, small/wide-angle X-ray scattering (SAXS/WAXS) and small-angle neutron scattering (SANS), were recently presented in Gumerov et al. (J. Comput. Chem., 2012, 33:1981). The use of these algorithms can speed up computation of scattering profiles in macromolecular structure refinement protocols. However, these protocols often employ an iterative gradient-based optimization procedure, which then requires derivatives of the profile with respect to atomic coordinates. An extension to one of the algorithms is presented which allows accurate, O(N) cost computation of the derivatives along with the scattering profile. Computational results show orders of magnitude improvement in computational efficiency, while maintaining prescribed accuracy. This opens the possibility to efficiently integrate small-angle scattering data into structure determination and refinement of macromolecular systems.

2013-05-25T00:00:00Z Keceli, Fuat Vishkin, Uzi http://hdl.handle.net/1903/13893 2013-05-22T02:31:50Z 2011-01-01T00:00:00Z

Title: XMTSim: A Simulator of the XMT Many-core Architecture Authors: Keceli, Fuat; Vishkin, Uzi Abstract: This paper documents the features and the design of XMTSim, the cycle-accurate simulator of the Explicit Multi-Threading (XMT) computer architecture. The Explicit Multi-Threading (XMT) is a general-purpose many-core computing platform, with the vision of a 1000-core chip that is easy to program but does not compromise on performance. XMTSim is a primary component in its publicly available toolchain along with an optimizing compiler. Research and experimentation enabled by the toolchain played a central role in supporting the ease-of-programming and performance aspects of the XMT architecture. The compiler and the simulator are also important milestones for an efficient programmer's workflow from PRAM algorithms to programs that run on the shared memory XMT hardware. This workflow is a key component in accomplishing the goal of ease-of-programming and performance. The applicability of the XMT simulator extends beyond specific XMT choices. It can be used to explore the much greater design space of shared memory many-cores by system researchers or by programmers. As the toolchain can practically run on any computer, it provides a supportive environment for teaching parallel algorithmic thinking with a programming component.

2011-01-01T00:00:00Z 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