bluuebunny/crossref_metadata_2025 huggingface dataset:
RCDC
Authors: Devietti Joseph , Nelson Jacob , Bergan Tom , Ceze Luis , Grossman Dan
Published: October 2012

Providing deterministic execution significantly simplifies the debugging, testing, replication, and deployment of multithreaded programs. Recent work has developed deterministic multiprocessor architectures as well as compiler and runtime systems that enforce determinism in current hardware. Such work has incidentally imposed strong memory-ordering properties. Historically, memory ordering has been relaxed in favor of higher performance in shared memory multiprocessors and, interestingly, determinism exacerbates the cost of strong memory ordering. Consequently, we argue that relaxed memory ordering is vital to achieving faster deterministic execution.

This paper introduces RCDC, a deterministic multiprocessor architecture that takes advantage of relaxed memory orderings to provide high-performance deterministic execution with low hardware complexity. RCDC has two key innovations: a hybrid HW/SW approach to enforcing determinism; and a new deterministic execution strategy that leverages data-race-free-based memory models (e.g., the models for Java and C++) to improve performance and scalability without sacrificing determinism, even in the presence of races. In our hybrid HW/SW approach, the only hardware mechanisms required are software-controlled store buffering and support for precise instruction counting; we do not require speculation. A runtime system uses these mechanisms to enforce determinism for arbitrary programs.

We evaluate RCDC using PARSEC benchmarks and show that relaxing memory ordering leads to performance and scalability close to nondeterministic execution without requiring any form of speculation. We also compare our new execution strategy to one based on TSO (total-store-ordering) and show that some applications benefit significantly from the extra relaxation. We also evaluate a software-only implementation of our new deterministic execution strategy.
Specifying and checking semantic atomicity for multithreaded programs
Authors: Burnim Jacob , Necula George , Sen Koushik
Published: October 2012

In practice, it is quite difficult to write correct multithreaded programs due to the potential for unintended and nondeterministic interference between parallel threads. A fundamental correctness property for such programs is atomicity---a block of code in a program is atomic if, for any parallel execution of the program, there is an execution with the same overall program behavior in which the block is executed serially.

We propose semantic atomicity, a generalization of atomicity with respect to a programmer-defined notion of equivalent behavior. We propose an assertion framework in which a programmer can use bridge predicates to specify noninterference properties at the level of abstraction of their application. Further, we propose a novel algorithm for systematically testing atomicity specifications on parallel executions with a bounded number of interruptions---i.e. atomic blocks whose execution is interleaved with that of other threads. We further propose a set of sound heuristics and optional user annotations that increase the efficiency of checking atomicity specifications in the common case where the specifications hold.

We have implemented our assertion framework for specifying and checking semantic atomicity for parallel Java programs, and we have written semantic atomicity specifications for a number of benchmarks. We found that using bridge predicates allowed us to specify the natural and intended atomic behavior of a wider range of programs than did previous approaches. Further, in checking our specifications, we found several previously unknown bugs, including in the widely-used java.util.concurrent library.
Mnemosyne
Authors: Volos Haris , Tack Andres Jaan , Swift Michael M.
Published: October 2012

New storage-class memory (SCM) technologies, such as phase-change memory, STT-RAM, and memristors, promise user-level access to non-volatile storage through regular memory instructions. These memory devices enable fast user-mode access to persistence, allowing regular in-memory data structures to survive system crashes.

In this paper, we present Mnemosyne, a simple interface for programming with persistent memory. Mnemosyne addresses two challenges: how to create and manage such memory, and how to ensure consistency in the presence of failures. Without additional mechanisms, a system failure may leave data structures in SCM in an invalid state, crashing the program the next time it starts.

In Mnemosyne, programmers declare global persistent data with the keyword "pstatic" or allocate it dynamically. Mnemosyne provides primitives for directly modifying persistent variables and supports consistent updates through a lightweight transaction mechanism. Compared to past work on disk-based persistent memory, Mnemosyne reduces latency to storage by writing data directly to memory at the granularity of an update rather than writing memory pages back to disk through the file system. In tests emulating the performance characteristics of forthcoming SCMs, we show that Mnemosyne can persist data as fast as 3 microseconds. Furthermore, it provides a 35 percent performance increase when applied in the OpenLDAP directory server. In microbenchmark studies we find that Mnemosyne can be up to 1400% faster than alternative persistence strategies, such as Berkeley DB or Boost serialization, that are designed for disks.
NV-Heaps
Authors: Coburn Joel , Caulfield Adrian M. , Akel Ameen , Grupp Laura M. , Gupta Rajesh K. , Jhala Ranjit , Swanson Steven
Published: October 2012

Persistent, user-defined objects present an attractive abstraction for working with non-volatile program state. However, the slow speed of persistent storage (i.e., disk) has restricted their design and limited their performance. Fast, byte-addressable, non-volatile technologies, such as phase change memory, will remove this constraint and allow programmers to build high-performance, persistent data structures in non-volatile storage that is almost as fast as DRAM. Creating these data structures requires a system that is lightweight enough to expose the performance of the underlying memories but also ensures safety in the presence of application and system failures by avoiding familiar bugs such as dangling pointers, multiple free()s, and locking errors. In addition, the system must prevent new types of hard-to-find pointer safety bugs that only arise with persistent objects. These bugs are especially dangerous since any corruption they cause will be permanent.

We have implemented a lightweight, high-performance persistent object system called NV-heaps that provides transactional semantics while preventing these errors and providing a model for persistence that is easy to use and reason about. We implement search trees, hash tables, sparse graphs, and arrays using NV-heaps, BerkeleyDB, and Stasis. Our results show that NV-heap performance scales with thread count and that data structures implemented using NV-heaps out-perform BerkeleyDB and Stasis implementations by 32x and 244x, respectively, by avoiding the operating system and minimizing other software overheads. We also quantify the cost of enforcing the safety guarantees that NV-heaps provide and measure the costs of NV-heap primitive operations.
Mementos
Authors: Ransford Benjamin , Sorber Jacob , Fu Kevin
Published: October 2012

Transiently powered computing devices such as RFID tags, kinetic energy harvesters, and smart cards typically rely on programs that complete a task under tight time constraints before energy starvation leads to complete loss of volatile memory. Mementos is a software system that transforms general-purpose programs into interruptible computations that are protected from frequent power losses by automatic, energy-aware state checkpointing. Mementos comprises a collection of optimization passes for the LLVM compiler infrastructure and a linkable library that exercises hardware support for energy measurement while managing state checkpoints stored in nonvolatile memory. We evaluate Mementos against diverse test cases in a trace-driven simulator of transiently powered RFID-scale devices. Although Mementos's energy checks increase run time when energy is plentiful, they allow Mementos to safely suspend execution when energy dwindles, effectively spreading computation across zero or more power failures. This paper's contributions are: a study of the runtime environment for programs on RFID-scale devices; an energy-aware state checkpointing system for these devices that is implemented for the MSP430 family of microcontrollers; and a trace-driven simulator of transiently powered RFID-scale devices.
Blink
Authors: Sharma Navin , Barker Sean , Irwin David , Shenoy Prashant
Published: October 2012

Reducing the energy footprint of data centers continues to receive significant attention due to both its financial and environmental impact. There are numerous methods that limit the impact of both factors, such as expanding the use of renewable energy or participating in automated demand-response programs. To take advantage of these methods, servers and applications must gracefully handle intermittent constraints in their power supply. In this paper, we propose blinking---metered transitions between a high-power active state and a low-power inactive state---as the primary abstraction for conforming to intermittent power constraints. We design Blink, an application-independent hardware-software platform for developing and evaluating blinking applications, and define multiple types of blinking policies. We then use Blink to design BlinkCache, a blinking version of memcached, to demonstrate the effect of blinking on an example application. Our results show that a load-proportional blinking policy combines the advantages of both activation and synchronous blinking for realistic Zipf-like popularity distributions and wind/solar power signals by achieving near optimal hit rates (within 15% of an activation policy), while also providing fairer access to the cache (within 2% of a syn- chronous policy) for equally popular objects.
Flikker
Authors: Liu Song , Pattabiraman Karthik , Moscibroda Thomas , Zorn Benjamin G.
Published: October 2012

Energy has become a first-class design constraint in computer systems. Memory is a significant contributor to total system power. This paper introduces Flikker, an application-level technique to reduce refresh power in DRAM memories. Flikker enables developers to specify critical and non-critical data in programs and the runtime system allocates this data in separate parts of memory. The portion of memory containing critical data is refreshed at the regular refresh-rate, while the portion containing non-critical data is refreshed at substantially lower rates. This partitioning saves energy at the cost of a modest increase in data corruption in the non-critical data. Flikker thus exposes and leverages an interesting trade-off between energy consumption and hardware correctness. We show that many applications are naturally tolerant to errors in the non-critical data, and in the vast majority of cases, the errors have little or no impact on the application's final outcome. We also find that Flikker can save between 20-25% of the power consumed by the memory sub-system in a mobile device, with negligible impact on application performance. Flikker is implemented almost entirely in software, and requires only modest changes to the hardware.
2ndStrike
Authors: Gao Qi , Zhang Wenbin , Chen Zhezhe , Zheng Mai , Qin Feng
Published: October 2012

Concurrency bugs are becoming increasingly prevalent in the multi-core era. Recently, much research has focused on data races and atomicity violation bugs, which are related to low-level memory accesses. However, a large number of concurrency typestate bugs such as "invalid reads to a closed file from a different thread" are under-studied. These concurrency typestate bugs are important yet challenging to study since they are mostly relevant to high-level program semantics.

This paper presents 2ndStrike, a method to manifest hidden concurrency typestate bugs in software testing. Given a state machine describing correct program behavior on certain object typestates, 2ndStrike profiles runtime events related to the typestates and thread synchronization. Based on the profiling results, 2ndStrike then identifies bug candidates, each of which is a pair of runtime events that would cause typestate violation if the event order is reversed. Finally, 2ndStrike re-executes the program with controlled thread interleaving to manifest bug candidates.

We have implemented a prototype of 2ndStrike on Linux and have illustrated our idea using three types of concurrency typestate bugs, including invalid file operation, invalid pointer dereference, and invalid lock operation. We have evaluated 2ndStrike with six real world bugs (including one previously unknown bug) from three open-source server and desktop programs (i.e., MySQL, Mozilla, pbzip2). Our experimental results show that 2ndStrike can effectively and efficiently manifest all six software bugs, most of which are difficult or impossible to manifest using stress testing or active testing techniques that are based on data race/atomicity violation. Additionally, 2ndStrike reports no false positives, provides detailed bug reports for each manifested bug, and can consistently reproduce the bug after manifesting it once.
ConSeq
Authors: Zhang Wei , Lim Junghee , Olichandran Ramya , Scherpelz Joel , Jin Guoliang , Lu Shan , Reps Thomas
Published: October 2012

Concurrency bugs are caused by non-deterministic interleavings between shared memory accesses. Their effects propagate through data and control dependences until they cause software to crash, hang, produce incorrect output, etc. The lifecycle of a bug thus consists of three phases: (1) triggering, (2) propagation, and (3) failure.

Traditional techniques for detecting concurrency bugs mostly focus on phase (1)--i.e., on finding certain structural patterns of interleavings that are common triggers of concurrency bugs, such as data races. This paper explores a consequence-oriented approach to improving the accuracy and coverage of state-space search and bug detection. The proposed approach first statically identifies potential failure sites in a program binary (i.e., it first considers a phase (3) issue). It then uses static slicing to identify critical read instructions that are highly likely to affect potential failure sites through control and data dependences (phase (2)). Finally, it monitors a single (correct) execution of a concurrent program and identifies suspicious interleavings that could cause an incorrect state to arise at a critical read and then lead to a software failure (phase (1)).

ConSeq's backwards approach, (3)!(2)!(1), provides advantages in bug-detection coverage and accuracy but is challenging to carry out. ConSeq makes it feasible by exploiting the empirical observationthat phases (2) and (3) usually are short and occur within one thread. Our evaluation on large, real-world C/C++ applications shows that ConSeq detects more bugs than traditional approaches and has a much lower false-positive rate.
S2E
Authors: Chipounov Vitaly , Kuznetsov Volodymyr , Candea George
Published: October 2012

This paper presents S2E, a platform for analyzing the properties and behavior of software systems. We demonstrate S2E's use in developing practical tools for comprehensive performance profiling, reverse engineering of proprietary software, and bug finding for both kernel-mode and user-mode binaries. Building these tools on top of S2E took less than 770 LOC and 40 person-hours each.

S2E's novelty consists of its ability to scale to large real systems, such as a full Windows stack. S2E is based on two new ideas: selective symbolic execution, a way to automatically minimize the amount of code that has to be executed symbolically given a target analysis, and relaxed execution consistency models, a way to make principled performance/accuracy trade-offs in complex analyses. These techniques give S2E three key abilities: to simultaneously analyze entire families of execution paths, instead of just one execution at a time; to perform the analyses in-vivo within a real software stack--user programs, libraries, kernel, drivers, etc.--instead of using abstract models of these layers; and to operate directly on binaries, thus being able to analyze even proprietary software.

Conceptually, S2E is an automated path explorer with modular path analyzers: the explorer drives the target system down all execution paths of interest, while analyzers check properties of each such path (e.g., to look for bugs) or simply collect information (e.g., count page faults). Desired paths can be specified in multiple ways, and S2E users can either combine existing analyzers to build a custom analysis tool, or write new analyzers using the S2E API.
Rethinking the library OS from the top down
Authors: Porter Donald E. , Boyd-Wickizer Silas , Howell Jon , Olinsky Reuben , Hunt Galen C.
Published: October 2012

This paper revisits an old approach to operating system construc-tion, the library OS, in a new context. The idea of the library OS is that the personality of the OS on which an application depends runs in the address space of the application. A small, fixed set of abstractions connects the library OS to the host OS kernel, offering the promise of better system security and more rapid independent evolution of OS components.

We describe a working prototype of a Windows 7 library OS that runs the latest releases of major applications such as Microsoft Excel, PowerPoint, and Internet Explorer. We demonstrate that desktop sharing across independent, securely isolated, library OS instances can be achieved through the pragmatic reuse of net-working protocols. Each instance has significantly lower overhead than a full VM bundled with an application: a typical application adds just 16MB of working set and 64MB of disk footprint. We contribute a new ABI below the library OS that enables application mobility. We also show that our library OS can address many of the current uses of hardware virtual machines at a fraction of the overheads. This paper describes the first working prototype of a full commercial OS redesigned as a library OS capable of running significant applications. Our experience shows that the long-promised benefits of the library OS approach better protection of system integrity and rapid system evolution are readily obtainable.
Looking back on the language and hardware revolutions
Authors: Esmaeilzadeh Hadi , Cao Ting , Xi Yang , Blackburn Stephen M. , McKinley Kathryn S.
Published: October 2012

This paper reports and analyzes measured chip power and performance on five process technology generations executing 61 diverse benchmarks with a rigorous methodology. We measure representative Intel IA32 processors with technologies ranging from 130nm to 32nm while they execute sequential and parallel benchmarks written in native and managed languages. During this period, hardware and software changed substantially: (1) hardware vendors delivered chip multiprocessors instead of uniprocessors, and independently (2) software developers increasingly chose managed languages instead of native languages. This quantitative data reveals the extent of some known and previously unobserved hardware and software trends. Two themes emerge.

(I) Workload: The power, performance, and energy trends of native workloads do not approximate managed workloads. For example, (a) the SPEC CPU2006 native benchmarks on the i7 (45) and i5 (32) draw significantly less power than managed or scalable native benchmarks; and (b) managed runtimes exploit parallelism even when running single-threaded applications. The results recommend architects always include native and managed workloads when designing and evaluating energy efficient hardware.

(II) Architecture: Clock scaling, microarchitecture, simultaneous multithreading, and chip multiprocessors each elicit a huge variety of power, performance, and energy responses. This variety and the difficulty of obtaining power measurements recommends exposing on-chip power meters and when possible structure specific power meters for cores, caches, and other structures. Just as hardware event counters provide a quantitative grounding for performance innovations, power meters are necessary for optimizing energy.
Exploring circuit timing-aware language and compilation
Authors: Hoang Giang , Findler Robby Bruce , Joseph Russ
Published: October 2012

By adjusting the design of the ISA and enabling circuit timing-sensitive optimizations in a compiler, we can more effectively exploit timing speculation. While there has been growing interest in systems that leverage circuit-level timing speculation to improve the performance and power-efficiency of processors, most of the innovation has been at the microarchitectural level. We make the observation that some code sequences place greater demand on circuit timing deadlines than others. Furthermore, by selectively replacing these codes with instruction sequences which are semantically equivalent but reduce activity on timing critical circuit paths, we can trigger fewer timing errors and hence reduce recovery costs.
On-the-fly elimination of dynamic irregularities for GPU computing
Authors: Zhang Eddy Z. , Jiang Yunlian , Guo Ziyu , Tian Kai , Shen Xipeng
Published: October 2012

The power-efficient massively parallel Graphics Processing Units (GPUs) have become increasingly influential for general-purpose computing over the past few years. However, their efficiency is sensitive to dynamic irregular memory references and control flows in an application. Experiments have shown great performance gains when these irregularities are removed. But it remains an open question how to achieve those gains through software approaches on modern GPUs.

This paper presents a systematic exploration to tackle dynamic irregularities in both control flows and memory references. It reveals some properties of dynamic irregularities in both control flows and memory references, their interactions, and their relations with program data and threads. It describes several heuristics-based algorithms and runtime adaptation techniques for effectively removing dynamic irregularities through data reordering and job swapping. It presents a framework, G-Streamline, as a unified software solution to dynamic irregularities in GPU computing. G-Streamline has several distinctive properties. It is a pure software solution and works on the fly, requiring no hardware extensions or offline profiling. It treats both types of irregularities at the same time in a holistic fashion, maximizing the whole-program performance by resolving conflicts among optimizations. Its optimization overhead is largely transparent to GPU kernel executions, jeopardizing no basic efficiency of the GPU application. Finally, it is robust to the presence of various complexities in GPU applications. Experiments show that G-Streamline is effective in reducing dynamic irregularities in GPU computing, producing speedups between 1.07 and 2.5 for a variety of applications.
The cloud will change everything
Authors: Larus James R.
Published: October 2012

Cloud computing is fast on its way to becoming a meaningless, oversold marketing slogan. In the midst of this hype, it is easy to overlook the fundamental change that is occurring. Computation, which used to be confined to the machine beside your desk, is increasingly centralized in vast shared facilities and at the same time liberated by battery-powered, wireless devices. Performance, security, and reliability are no longer problems that can be considered in isolation -- the wires and software connecting pieces offer more challenges and opportunities than components themselves. The eXtreme Computing Group (XCG) in Microsoft Research is taking a holistic approach to research in this area, by bring together researchers and developers with expertise in data center design, computer architecture, operating systems, computer security, programming language, mobile computation, and user interfaces to tackle the challenges of cloud computing.
Improving software diagnosability via log enhancement
Authors: Yuan Ding , Zheng Jing , Park Soyeon , Zhou Yuanyuan , Savage Stefan
Published: October 2012

Diagnosing software failures in the field is notoriously difficult, in part due to the fundamental complexity of trouble-shooting any complex software system, but further exacerbated by the paucity of information that is typically available in the production setting. Indeed, for reasons of both overhead and privacy, it is common that only the run-time log generated by a system (e.g., syslog) can be shared with the developers. Unfortunately, the ad-hoc nature of such reports are frequently insufficient for detailed failure diagnosis. This paper seeks to improve this situation within the rubric of existing practice. We describe a tool, LogEnhancer that automatically "enhances" existing logging code to aid in future post-failure debugging. We evaluate LogEnhancer on eight large, real-world applications and demonstrate that it can dramatically reduce the set of potential root failure causes that must be considered during diagnosis while imposing negligible overheads.
A case for neuromorphic ISAs
Authors: Hashmi Atif , Nere Andrew , Thomas James Jamal , Lipasti Mikko
Published: October 2012

The desire to create novel computing systems, paired with recent advances in neuroscientific understanding of the brain, has led researchers to develop neuromorphic architectures that emulate the brain. To date, such models are developed, trained, and deployed on the same substrate. However, excessive co-dependence between the substrate and the algorithm prevents portability, or at the very least requires reconstructing and retraining the model whenever the substrate changes. This paper proposes a well-defined abstraction layer -- the Neuromorphic instruction set architecture, or NISA -- that separates a neural application's algorithmic specification from the underlying execution substrate, and describes the Aivo framework, which demonstrates the concrete advantages of such an abstraction layer. Aivo consists of a NISA implementation for a rate-encoded neuromorphic system based on the cortical column abstraction, a state-of-the-art integrated development and runtime environment (IDE), and various profile-based optimization tools. Aivo's IDE generates code for emulating cortical networks on the host CPU, multiple GPGPUs, or as boolean functions. Its runtime system can deploy and adaptively optimize cortical networks in a manner similar to conventional just-in-time compilers in managed runtime systems (e.g. Java, C#).

We demonstrate the abilities of the NISA abstraction by constructing a cortical network model of the mammalian visual cortex, deploying on multiple execution substrates, and utilizing the various optimization tools we have created. For this hierarchical configuration, Aivo's profiling based network optimization tools reduce the memory footprint by 50% and improve the execution time by a factor of 3x on the host CPU. Deploying the same network on a single GPGPU results in a 30x speedup. We further demonstrate that a speedup of 480x can be achieved by deploying a massively scaled cortical network across three GPGPUs. Finally, converting a trained hierarchical network to C/C++ boolean constructs on the host CPU results in 44x speedup.
Ensuring operating system kernel integrity with OSck
Authors: Hofmann Owen S. , Dunn Alan M. , Kim Sangman , Roy Indrajit , Witchel Emmett
Published: October 2012

Kernel rootkits that modify operating system state to avoid detection are a dangerous threat to system security. This paper presents OSck, a system that discovers kernel rootkits by detecting malicious modifications to operating system data. OSck integrates and extends existing techniques for detecting rootkits, and verifies safety properties for large portions of the kernel heap with minimal overhead. We deduce type information for verification by analyzing unmodified kernel source code and in-memory kernel data structures.

High-performance integrity checks that execute concurrently with a running operating system create data races, and we demonstrate a deterministic solution for ensuring kernel memory is in a consistent state. We introduce two new classes of kernel rootkits that are undetectable by current systems, motivating the need for the OSck API that allows kernel developers to conveniently specify arbitrary integrity properties.
Multilevel local search algorithms for modularity clustering
Authors: Rotta Randolf , Noack Andreas
Published: October 2012

Modularity is a widely used quality measure for graph clusterings. Its exact maximization is NP-hard and prohibitively expensive for large graphs. Popular heuristics first perform a coarsening phase, where local search starting from singleton clusters is used to compute a preliminary clustering, and then optionally a refinement phase, where this clustering is improved by moving vertices between clusters. As a generalization, multilevel heuristics coarsen in several stages, and refine by moving entire clusters from each of these stages, not only individual vertices.

This article organizes existing and new single-level and multilevel heuristics into a coherent design space, and compares them experimentally with respect to their effectiveness (achieved modularity) and runtime. For coarsening by iterated cluster joining, it turns out that the most widely used criterion for joining clusters (modularity increase) is outperformed by other simple criteria, that a recent multistep algorithm [Schuetz and Caflisch 2008] is no improvement over simple single-step coarsening for these criteria, and that the recent multilevel coarsening by iterated vertex moving [Blondel et al. 2008] is somewhat faster but slightly less effective (with refinement). The new multilevel refinement is significantly more effective than the conventional single-level refinement or no refinement, in reasonable runtime.

A comparison with published benchmark results and algorithm implementations shows that multilevel local search heuristics, despite their relative simplicity, are competitive with the best algorithms in the literature.
Motorcycle graphs
Authors: Huber Stefan , Held Martin
Published: October 2012

simple but very efficient algorithm for computing motorcycle graphs. An analysis of the mean trace length of
n
random motorcycles suggests that, on average, a motorcycle crosses only a constant number of cells within a √
n
× √
n
rectangular grid, provided that the motorcycles are distributed sufficiently uniformly over the area covered by the grid. This analysis motivates a simple algorithm for computing motorcycle graphs: We use the standard priority-queue--based algorithm and enhance it with geometric hashing by means of a rectangular grid. If the motorcycles are distributed sufficiently uniformly, then our stochastic analysis predicts an
O
(
n
log
n
) runtime. Indeed, extensive experiments run on 22,000 synthetic and real-world datasets confirm a runtime of less than 10
−5
n
log
n
seconds for the vast majority of our datasets on a standard PC. Further experiments with our software, Moca, also confirm the mean trace length and average number of cells crossed by a motorcycle, as predicted by our analysis. This makes Moca the first implementation that is efficient enough to be applied in practice for computing motorcycle graphs of large datasets. Actually, it is easy to extend Moca to make it compute a generalized version of the original motorcycle graph, thus enabling a significantly larger field of applications.
An experimental comparison of single-sided preference matching algorithms
Authors: Michail Dimitrios
Published: October 2012

applicant provides a preference list, which may contain ties, ranking a subset of the posts. Different optimization criteria may be defined, which depend on the desired solution properties. The main focus of this work is to assess the quality of matchings computed by rank-maximal and popular matching algorithms and compare this with the minimum weight matching algorithm, which is a standard matching algorithm that is used in practice.

Both rank-maximal and popular matching algorithms use common algorithmic techniques, which makes them excellent candidates for a running time comparison. Since popular matchings do not always exist, we also study the unpopularity of matchings computed by the aforementioned algorithms. Finally, extra criteria like total weight and cardinality are included, due to their importance in practice. All experiments are performed using structured random instances as well as instances created using real-world datasets.
Effective out-of-core parallel delaunay mesh refinement using off-the-shelf software
Authors: Kot Andriy , Chernikov Andrey N. , Chrisochoides Nikos P.
Published: October 2012

We present three related out-of-core parallel mesh generation algorithms and their implementations for small size computational clusters. Computing out-of-core permits to solve larger problems than otherwise possible on the same hardware setup. Also, when using shared computing resources with high demand, a problem can take longer to compute in terms of wall-clock time when using an in-core algorithm on many nodes instead of using an out-of-core algorithm on few nodes. The difference is due to wait-in-queue delays that can grow exponentially to the number of requested nodes. In one specific case, using our best method and only 16 nodes it can take several times less wall-clock time to generate a 2 billion element mesh than to generate the same size mesh in-core with 121 nodes.

Although our best out-of-core method exhibits unavoidable overheads (could be as low as 19% in some cases) over the corresponding in-core method (for mesh sizes that fit completely in-core), this is a modest and expected performance penalty. We evaluated our methods on traditional clusters of workstations as well as presented preliminary performance evaluation on emerging BlueWaters supercomputer.
Theory and practice of monotone minimal perfect hashing
Authors: Belazzougui Djamal , Boldi Paolo , Pagh Rasmus , Vigna Sebastiano
Published: October 2012

Minimal perfect hash functions have been shown to be useful to compress data in several data management tasks. In particular, order-preserving minimal perfect hash functions (Fox et al. 1991) have been used to retrieve the position of a key in a given list of keys; however, the ability to preserve any given order leads to an unavoidable Ω(
n
log
n
) lower bound on the number of bits required to store the function. Recently, it was observed (Belazzougui et al. 2009) that very frequently the keys to be hashed are sorted in their intrinsic (i.e., lexicographical) order. This is typically the case of dictionaries of search engines, list of URLs of Web graphs, and so on. We refer to this restricted version of the problem as
monotone minimal perfect hashing
. We analyze experimentally the data structures proposed in Belazzougui et al. [2009], and along our way we propose some new methods that, albeit asymptotically equivalent or worse, perform very well in practice and provide a balance between access speed, ease of construction, and space usage.
Four-dimensional hilbert curves for R-trees
Authors: Haverkort Herman , Walderveen Freek V.
Published: October 2012

Two-dimensional R-trees are a class of spatial index structures in which objects are arranged to enable fast window queries: report all objects that intersect a given query window. One of the most successful methods of arranging the objects in the index structure is based on sorting the objects according to the positions of their centers along a two-dimensional Hilbert space-filling curve. Alternatively, one may use the coordinates of the objects' bounding boxes to represent each object by a four-dimensional point, and sort these points along a four-dimensional Hilbert-type curve. In experiments by Kamel and Faloutsos and by Arge et al., the first solution consistently outperformed the latter when applied to point data, while the latter solution clearly outperformed the first on certain artificial rectangle data. These authors did not specify which four-dimensional Hilbert-type curve was used; many exist.

In this article, we show that the results of the previous articles can be explained by the choice of the four-dimensional Hilbert-type curve that was used and by the way it was rotated in four-dimensional space. By selecting a curve that has certain properties and choosing the right rotation, one can combine the strengths of the two-dimensional and the four-dimensional approach into one, while avoiding their apparent weaknesses. The effectiveness of our approach is demonstrated with experiments on various datasets. For real data taken from VLSI design, our new curve yields R-trees with query times that are better than those of R-trees that were obtained with previously used curves.
Solving maximum flow problems on real-world bipartite graphs
Authors: Negrucşeri Cosmin Silvestru , Pacsoşi Mircea BOGDAN , Stanley Barbara , Stein Clifford , Strat Cristian George
Published: October 2012

In this article, we present an experimental study of several maximum-flow algorithms in the context of unbalanced bipartite networks. Our experiments are motivated by a real-world problem of managing reservation-based inventory in Google content ad systems. We are interested in observing the performance of several push-relabel algorithms on our real-world datasets and also on some generated ones. Previous work suggested an important improvement for push-relabel algorithms on unbalanced bipartite networks: the two-edge push rule. We show how the two-edge push rule improves the running time. While no single algorithm dominates the results, we show there is one that has very robust performance in practice.
Approximation algorithms for speeding up dynamic programming and denoising aCGH data
Authors: Tsourakakis Charalampos E. , Peng Richard , Tsiarli Maria A. , Miller Gary L. , Schwartz Russell
Published: October 2012

The development of cancer is largely driven by the gain or loss of subsets of the genome, promoting uncontrolled growth or disabling defenses against it. Denoising array-based Comparative Genome Hybridization (aCGH) data is an important computational problem central to understanding cancer evolution. In this article, we propose a new formulation of the denoising problem that we solve with a “vanilla” dynamic programming algorithm, which runs inO(n2) units of time. Then, we propose two approximation techniques. Our first algorithm reduces the problem into a well-studied geometric problem, namely halfspace emptiness queries, and provides an ϵ additive approximation to the optimal objective value in Õ(n4/3;+Δlog (U/ϵ)) time, where Δ is an arbitrarily small positive constant andU= max{#8730;C,(|Pi|)i=1,…,n} (P=(P1,P2, …,Pn),Pi∈ ℝ, is the vector of the noisy aCGH measurements,Ca normalization constant). The second algorithm provides a (1 ± ϵ) approximation (multiplicative error) and runs inO(nlogn/ϵ) time. The algorithm decomposes the initial problem into a small (logarithmic) number of Monge optimization subproblems that we can solve in linear time using existing techniques.

Finally, we validate our model on synthetic and real cancer datasets. Our method consistently achieves superior precision and recall to leading competitors on the data with ground truth. In addition, it finds several novel markers not recorded in the benchmarks but supported in the oncology literature.
The forgotten majority of computing have-nots
Authors: Bakar Ahmad Zaki Abu
Published: October 2012

People have falsely regarded the computing working environment as dedicated to the confines of a building with availability of electricity, high-speed info-structure, and the latest computer technology. In reality, there are many computing have-nots in the real world living in challenged computing environments. Current computing curricula are designed to prepare graduates for more urban and best-case business scenarios where learning takes place within campus boundaries. To prepare computing graduates better to survive in harsh environments and to contribute meaningfully to society, their learning should also take place out of the classroom and into challenged computing environments where active and experiential learning could take place. Confronted with the harsh realities of life, students learn quickly to adapt themselves for survival and for their future career. Many generic skills can be reinforced here to make computing graduates more versatile, entrepreneurial, effective, and ever ready to face the real world.
Ubiquitous mobile phones are becoming indispensable
Authors: Gupta Gireesh K
Published: October 2012

Mobile phones are ubiquitous today. The portable device has revolutionized the way we communicate with one another locally and globally. They have enabled the populace to be connected to one another in case of a crisis even from a remote area. Today real-time communication is possible at any time and from any part of the globe. Cell phones have become a necessity in today's digital global society, and are not just a symbol of social status anymore. In developing countries, they are being considered as the fifth necessity in addition to food, clothes, shelter, and education. In lieu of a static presentation, Prof. Knuth will conduct an interactive dialog with attendees, entitled "All Questions Answered".
TauRUs
Authors: Goldweber Michael
Published: October 2012

The TauRUs survey (Taulbee For the Rest of Us) is an attempt to capture data regarding the state of computer science education at non-Ph.D. granting institutions. Annually, the Taulbee survey reports on the state of computer science programs at Ph.D. granting institutions. What this survey attempts to answer is how well does Taulbee data represent non-Ph.D. programs? If Taulbee is not representative, what are the differences between the three cohorts of programs: Ph.D. granting programs (which include Masters and undergraduate programs), Masters granting programs (which also include undergraduate programs), and undergraduate only programs.
Optimizations generating Armstrong numbers
Authors: Rolfe Timothy J.
Published: October 2012

This article explores various optimizations that can be used to speed the discovery of Armstrong numbers (also known as Narcissistic numbers), which are
n
-digit numbers that are the sum of the
n
th
powers of their digits. Optimizations include comparing the parity of the least-significant digit of the number and that of the sum of its digits, using a dynamic programming approach for the powers of digits, examining the parity of the sum of digits excluding the least-significant digit, and computing forward bounds on the possible numbers and on the possible sums of
d

n

. The final optimization completes in about 2% of the time of the initial implementation.
Scalable SQL
Authors: Rys Michael
Published: October 2012

One of the leading motivators for NoSQL innovation is the desire to achieve very high scalability to handle the vagaries of Internet-size workloads. Yet many big social Web sites and many other Web sites and distributed tier 1 applications that require high scalability reportedly remain SQL-based for their core data stores and services. The question is, how do they do it?
Jim Gray - A Talk with THE SQL Guru and Architect
Authors: Gray Jim
Published: October 2012

Jim Gray is a distinguished engineer in Microsoft’s Scalable Servers Research Group and manager of our Bay Area Research Center. That doesn’t even start to do justice to the role Jim has played in the development of databases. You might know him as the guy behind Terra Service or Sky Server. We sat down with Jim for a couple of hours. Here’s the first part. We talk about everything about new database architectures to new trends in computing to his role in Terra Service.
Resurrecting the bullet point
Authors: Yaffe Philip
Published: October 2012

PowerPoint has come under attack in recent years. Well known figures such as Edward Tufte have castigated PowerPoint for corrupting minds and numbing thought. Some sociologists have condemned it for luring people away from listening to each other and communicating effectively. Scott Adams (author of Dilbert) often depicts PowerPoint as a facilitator of office dysfunction. From all this, you might think PowerPoint has badly wounded us and our society with its barrage of bullet points.
Deduplicating Devices Considered Harmful
Authors: Rosenthal David
Published: October 2012

During the research for their interesting paper, "Reliably Erasing Data From Flash-based Solid State Drives," delivered at the FAST (File and Storage Technology) workshop at San Jose in February, Michael Wei and his co-authors from the University of California, San Diego discovered that at least one flash controller, the SandForce SF-1200, was by default doing block-level deduplication of data written to it. The SF-1200 is used in SSDs (solid-state disks) from, among others, Corsair, ADATA, and Mushkin.
Interviewing Techniques
Authors: Neville-Neil George
Published: October 2012

My work group has just been given approval to hire four new programmers, and now all of us have to interview people, both on the phone and in person. I hate interviewing people. I never know what to ask. I’ve also noticed that people tend to be careless with the truth when writing their resumes. We’re considering a programming test for our next round of interviewees, because we realized that some previous candidates clearly couldn’t program their way out of a paper bag. There have to be tricks to speeding up hiring without compromising whom we hire.
The Robustness Principle Reconsidered
Authors: Allman Eric
Published: October 2012

In 1981, Jon Postel formulated the Robustness Principle, also known as Postel’s Law, as a fundamental implementation guideline for the then-new TCP. The intent of the Robustness Principle was to maximize interoperability between network service implementations, particularly in the face of ambiguous or incomplete specifications. If every implementation of some service that generates some piece of protocol did so using the most conservative interpretation of the specification and every implementation that accepted that piece of protocol interpreted it using the most generous interpretation, then the chance that the two services would be able to talk with each other would be maximized. Experience with the Arpanet had shown that getting independently developed implementations to interoperate was difficult, and since the Internet was expected to be much larger than the Arpanet, the old ad-hoc methods needed to be enhanced.
Parallelism orchestration using DoPE
Authors: Raman Arun , Kim Hanjun , Oh Taewook , Lee Jae W. , August David I.
Published: October 2012

In writing parallel programs, programmers expose parallelism and optimize it to meet a particular performance goal on a single platform under an assumed set of workload characteristics. In the field, changing workload characteristics, new parallel platforms, and deployments with different performance goals make the programmer's development-time choices suboptimal. To address this problem, this paper presents the Degree of Parallelism Executive (DoPE), an API and run-time system that separates the concern of exposing parallelism from that of optimizing it. Using the DoPE API, the application developer expresses parallelism options. During program execution, DoPE's run-time system uses this information to dynamically optimize the parallelism options in response to the facts on the ground. We easily port several emerging parallel applications to DoPE's API and demonstrate the DoPE run-time system's effectiveness in dynamically optimizing the parallelism for a variety of performance goals.