Search

This work proposes DUELMERGE, a stable merging algorithm that is asymptotically optimal in the number of comparisons and performs O (n log2 (n) moves. Unlike other partition-based algorithms, we only allow blocks of equal sizes to be swapped, which reduces the number of moves required. We performed experiments comparing DUELMERGE against a number of baselines including RECMERGE, the standard merging solution for programming languages such as C, and some more recent approaches. The results show that our proposed algorithm performs fewer moves than other stable solutions. Experiments employing DUELMERGE within MergeSort confirmed our positive results in terms of moves, comparisons and runtime. [ABSTRACT FROM AUTHOR]

This article presents the detailed description of a GPU-based multi-unit deadlock detection methodology, GPU-LMDDA with 12 pieces of pseudo code. Our design utilises the massively parallel hardware of the GPU to perform computations of deadlock detection in multi-unit resource systems. As a result, it is able to overcome the major limitations of prior software and hardware-based solutions by handling thousands of processes and resources concurrently. GPU-LMDDA employs a bit-vector technique with a novel bit-matrix multiplication algorithm to store and perform computations on algorithm matrices, thus decreasing the memory footprint and maximizing throughput. Our design treats deadlock detection as a service to the operating system by requiring minimal interaction with the CPU. By treating deadlock detection as an interactive service, all matrix management and algorithm computation are handled by the GPU, freeing CPU compute cycles. Our algorithm is implemented on three GPU cards: Tesla C2050, Tesla K20c, and Titan X, which showed speedups of 3-434X against single-threaded CPU equivalents. As an interactive service to the CPU and with bit-vector technique, GPU-LMDDA provides significant speedups against CPU implementation for increasing number of resources and processes. [ABSTRACT FROM AUTHOR]

We give an account on the authors' experience and results from the software verification competition held at the Formal Methods 2012 conference. Competitions like this are meant to provide a benchmark for verification systems. It consisted of three algorithms which the authors have implemented in Java, specified with the Java Modeling Language, and verified using the KeY system. Building on our solutions, we argue that verification systems which target implementations in real-world programming languages better have powerful abstraction capabilities. Regarding the KeY tool, we explain features which, driven by the competition, have been freshly implemented to accommodate for these demands. [ABSTRACT FROM AUTHOR]