In this paper, we derive parameterized Chernoff bounds and show their applications for simplifying the analysis of some well-known probabilistic algorithms and data structures. The parameterized Chernoff bounds we provide give probability bounds that are powers of two, with a clean formulation of the relation between the constant in the exponent and the relative distance from the mean. In addition, we provide new simplified analyses with these bounds for hash tables, randomized routing, and a simplified, non-recursive adaptation of the Floyd-Rivest selection algorithm.

We provide and study several algorithms for sorting an array of n comparable distinct elements subject to probabilistic comparison errors. In this model, the comparison of two elements returns the wrong answer according to a fixed probability, p_e < 1/2, and otherwise returns the correct answer. The dislocation of an element is the distance between its position in a given (current or output) array and its position in a sorted array. There are various algorithms that can be utilized for sorting or near-sorting elements subject to probabilistic comparison errors, but these algorithms are not data oblivious because they all make heavy use of noisy binary searching. In this paper, we provide new methods for sorting with comparison errors that are data oblivious while avoiding the use of noisy binary search methods. In addition, we experimentally compare our algorithms and other sorting algorithms.

In this paper, we derive simplified Chernoff bounds with powers-of-two probabilities, and we show their uses in analyzing probabilistic algorithms.

This paper proposes a distributed flow-based routing technique in energy-harvesting wireless sensor networks (EHWSNs) in order to balance the energy consumptions by sending packets assigned to routers that are sent from sensors to base stations. The objective of the flow optimization problem is to minimize the total load factors of all the nodes and wireless links, which leads to sustainable management of the sensor networks that exploit renewable power from energy harvesting systems. We propose a novel algorithm based on tie-set graph theory where the underlying graph of an EHWSN is divided into a set of independent loops to significantly reduce the topological complexity, which simplifies the flow optimization problem to be solved in a distributed manner. Simulation experiments against the shortest-path and multi-path algorithms demonstrate that optimized packet flows by the proposed method realize the sustainable EHWSNs and maintain the useful life of storage devices with modest increase in total energy consumption by routings.

Scientific computing is only bound by the limits of Moore's Law and the scalability of high performance mathematical library implementations. Most mathematical libraries however tend to focus only on general inputs, limiting their potential performance and scalability by not tailoring their implementation to specific inputs, such as non-negative inputs. By removing this limitation it is possible to improve the performance and accuracy of a range of problems. In this paper we explore the limitations of hardware to improve accuracy of non-negative matrix multiply by specifically comparing implementations on the GPU and CPU and propose algorithmic solutions to improve accuracy. Next, we demonstrate a matrix multiply implementation that takes advantage of asymptotically fast matrix multiply algorithms, which have been shown to scale better than O(N3) matrix multiply implementations, and improve accuracy by up to a whole digit while increasing performance by up to 27% for matrices where the input is positive. Finally, we propose to extend the BLAS level 3 specification to non-negative matrices to allow easy integration of our solution and allow other library authors to implement their own solutions as part of an existing standard.

In this paper, we propose a mechanism for coping with double-link failures in an autonomous and distributed manner. We call it Tie-set Based Fault Tolerance (TBFT) because it utilizes tie-sets, which represent a set of the edges comprising a loop within the graph that represents the network. An autonomous distributed control method based on dividing a network into a set of tie-sets, whose union covers every edge in the network, has been verified to be more effective than traditional tree-based restoration techniques in case of single link failure. The proposed method efficiently and gracefully handle double-link failures and also decrease the communication overhead incurred during network configuration. We demonstrate these results by simulating and comparing TBFT with the traditional approach of using Rapid Spanning Tree Protocol (RSTP).

We present a new methodology for developing parallel distributed programs in a series of incremental steps. The methodology takes advantage of threads that are able to migrate through the network and thus are able to follow distributed data. This allows the data to be partitioned and distributed first, which guarantees that elements that are used together in a computation are collocated on the same node. Next, the loops in the code are tiled to minimize migration among nodes. After deciding on the location at which each loop is to execute, the necessary migration and remote access statements are inserted to make the code executable. This process is repeated based on feedback obtained from the execution, which may improve the overall performance by suggesting a different data distribution or a different coarseness of tiling. We illustrate the trade-offs and the performance using a well-known application with two different data distributions.

Matrix multiply is ubiquitous in scientific computing. Considerable effort has been spent on improving its performance. Once methods that make efficient use of the processor have been exhausted, methods that use less operations than the canonical matrix multiply must be explored. Combining the two methods yields a hybrid matrix multiply algorithm. Hybrid matrix multiply algorithms tend to be less accurate than the canonical matrix multiply implementation, leaving room for improvement. There are well-known techniques for improving accuracy, but they tend to be slow and it is not immediately obvious how best to apply them to hybrid algorithms without lowering performance. Previous attempts have focused on the bottom of the hybrid matrix multiply algorithm, modifying the high-performance matrix multiply implementation. In contrast, the top-down approach presented here does not require the modification of the high-performance matrix multiply implementation at the bottom, nor does it require modification of the fast asymptotic matrix multiply algorithm at the top. The three-level hybrid algorithm presented here not only has up to 10% better performance than the fastest high-performance matrix multiply, but is also more accurate.

With systems such as Road Runner, there is a trend in super computing to offload parallel tasks to special purpose co-processors, composed of many relatively simple scalar processors. The cheaper commodity class equivalent of such a processor would be the graphics card, potentially offering super computer power within the confines of a desktop PC. Graphics cards however are not without problems, these range from the lack of double precision on most cards to a fairly steep drop in performance for using double precision on others, the end result being that in order to utilize the graphics card the computation must be done using single precision. In this paper we propose a method whereby a whole digit of the accuracy lost in single precision matrix multiply can be regained with only a 7% loss in performance by applying a compensated summation algorithm in a manner previously unexplored, a manner in which, at first glance, shouldn't provide any benefit but empirical evidence will show that though the novel idea is simple, provides unexpected benefits in terms of accuracy at little cost to performance.

We present an approach to implementing and using global pointers in a distributed computing environment. The programmer is able to create pointer-based distributed data structures, which can then be used by sequential or parallel programs without having to differentiate between local and global pointers. Any reference to a remote address causes the process to either migrate to the remote host, where it continues its execution, or to perform a remote access operation. The decision is made automatically and fully transparently to the programmer. By using a hardware-supported memory checking mechanism, we avoid any overhead associated with the detection of remote references.

Program parallelization requires mapping computation and data to processing elements. Navigational Programming (NavP), based on the principle of migrating computations, offers a different approach than the conventional solutions that use a SPMD model. This paper focuses on data distribution for NavP. We introduce the Navigational Trace Graph (NTG), a mathematical structure that captures the alignment and distribution preferences of a sequential program. Graph partitioning is applied to NTGs to obtain data distribution solutions. The major advantage is that our methodology can focus exclusively on reducing communication overhead first and later determine the actual computation partition and parallelization, because NavP computations migrate freely across partitions. This is in stark contrast to SPMD, where the data partitioning imposes hard constraints on the threads because they are stationary. We present experimental results to demonstrate the effectiveness of our approach.

We show how a series of transformations can be applied to incrementally parallelize sequential programs. Our navigational programming (NavP) methodology is based on the principle of self-migrating computations and is truly incremental, in that each step represents a functioning program and every intermediate program is an improvement over its predecessor. The transformations are mechanical and straightforward to apply. We illustrate our methodology in the context of matrix multiplication. Our final stage is similar to the classical Gentleman's algorithm. The NavP methodology is conducive to new ways of thinking that lead to ease of programming and high performance.

We describe an environment for the distributed solution of iterative grid-based applications. The environment is built using the MESSENGERS mobile agent system. The main advantage of paradigm-oriented distributed computing is that the user only needs to specify the application-specific sequential code, while the underlying infrastructure takes care of the parallelization and distribution. The two paradigms discussed in this papers are: the finite difference method, and individual-based simulation. These paradigms present some interesting challenges, both in terms of performance (because they require frequent synchronized communication between nodes) and in terms of repeatability (because the mapping of the user space onto the network may change due to load balancing or due to changes in the underlying logical network). We describe their use, implementation, and performance within a mobile agent-based environment.

Sequential computations can benefit from a distributed environment consisting of a network of workstations through the use of a mobile agent system. We found significant performance improvement when sequential algorithms for solving large industrial problems are implemented using mobile agents. This is because raw data is distributed so that the cost of disk paging is completely eliminated, and a principle of "code moving to data" is followed to achieve efficient communication through the network. We argue that mobile agent systems provide a new level of abstraction in which application programming is made easier because the sequential algorithms remain essentially unchanged in mobile agent code.

This paper proposes a new approach to rollback-recovery for mobile agent systems, and describes its implementation in the MESSENGERS mobile agents system. The used checkpointing method allows the implementation of a space and time efficient, user-transparent rollback-recovery in heterogeneous distributed environments. Together with an efficient non-blocking system snapshot algorithm this checkpointing method is an attractive choice for implementing a rollback-recovery mechanism in a mobile agent system, because it exploits features specific to such systems during the recovery. This paper also presents an optimization technique, called concurrent checkpointing, that increases the effectiveness of the proposed rollback-recovery mechanism.

We describe the implementation underlying an environment for distributed computing that uses the concept of well-known paradigms. The main advantage of paradigm oriented distributed computing is that the user only needs to specify application-specific sequential code, while the underlying infrastructure takes care of the parallelization and distribution. The main features of the proposed approach, called PODC, which differentiate it from other approaches, are the following: (1) it is intended for loosely-coupled network environments, not specialized multiprocessors; (2) it is based on an infrastructure of mobile agents; (3) it supports programming in C, rather than a functional or special-purpose language, and (4) it provides a Web based interactive graphics interface through which programs are constructed, invoked, and monitored. The three paradigms presently supported in PODC are the bag-of-tasks, the branch-and-bound and genetic programming. We describe their implementation and performance within the mobile agent based PODC environment.

This paper presents a new checkpointing algorithm that guarantees the semantics of reliable communication channels despite the crash and recovery of processes. This algorithm requires O(n+m) communication messages, where n is the number of participating processes, and m is the number of "late" messages. The algorithm is nonblocking, requires minimal message logging, and has minimal stable storage requirements. This algorithm is also scalable, simple transparent to the user, and facilitates fast recovery. By introducing suitable delay in the checkpointing process, the parameter m can be made small. We also describe a variant of the algorithm that requires only O(n) messages, at a cost of O(n) additional storage for each process.

Messengers are autonomous objects, each capable of navigating through the underlying network and performing various tasks at each node. Messenger applications are written using navigational commands rather than the send/receive primitives of conventional message-passing approaches. In this paper we contrast the two programming styles. The navigational style generally results in a smaller semantic gap between abstract algorithm descriptions and their actual implementations, which makes programs easier to construct, understand, and maintain. Other advantages of the navigational programming style include the ability to compute in unknown or dynamically changing network topologies.

We present an algorithm for testing the inscribability of a trivalent polyhedron, or, equivalently, testing the circumscribability of a simplicial polyhedron. Our algorithm runs in linear time, using only low-precision integer arithmetic. The algorithm is based on a purely combinatorial characterization of inscribable trivalent polyhedra.

An improved and general approach to connected-component labeling of images is presented. The algorithm presented in this paper processes images in predetermined order , which means that the processing order depends only on the image representation scheme and not on specific properties of the image. The algorithm handles a wide variety of image representation schemes (rasters, run lengths, quadrees, bintrees, etc.). How to adapt the standard UNION-FIND algorithm to permit reuse of temporary labels is shown. This is done using a technique called age balancing , in which, when two labels are merged, the older label becomes the father of the younger label. This technique can be made to coexist with the more conventional rule of weight balancing , in which the label with more descendants becomes the father of the label with fewer descendants. Various image scanning orders are examined and classified. It is also shown that when the algorithm is specialized to a pixel array scanned in raster order, the total processing time is linear in the number of pixels. The linear-time processing time follows from a special property of the UNION-FIND algorithm, which may be of independent interest. This property states that under certain restrictions on the input, UNION-FIND runs in time linear in the number of FIND and UNION operations. Under these restrictions, linear-time performance can be achieved without resorting to the more complicated Gabow-Tarjan algorithm for disjoint set union.

We show that nondegenerate Delaunay triangulations satisfy a combinatorial property called 1-toughness. A graph with set of sites S is 1-tough if for any set P ⊆ S, c(S - P) ≤ |S|, where c(S - P) is the number of components of the subgraph induced by the complement of P and |P| is the number of sites in P. We also show that, under the same conditions, the number of interior components of S - P is at most |P| - 2. These appear to be the first nontrivial properties of a purely combinatorial nature to be established for Delaunay triangulations. We give examples to show that these bounds can be attained, and we state and prove several corollaries. In particular, we show that maximal planar graphs inscribable in a sphere are 1-tough.