Search

Current mathematical modeling methods for the spreading of infectious diseases are too simplified and do not scale well. We present the Simulator of Epidemic Evolution in Complex Networks (SEECN), an efficient simulator of detailed individual-based models by parameterizing separate dynamics operators, which are iteratively applied to the contact network. We reduce the network generator΄s computational complexity, improve cache efficiency and parallelize the simulator. To evaluate its running time we experiment with an HIV epidemic model that incorporates up to one million homosexual men in a scale-free network, including hierarchical community structure, social dynamics and multi-stage intranode progression. We find that the running times are feasible, on the order of minutes, and argue that SEECN can be used to study realistic epidemics and its properties experimentally, in contrast to defining and solving ever more complicated mathematical models as is the current practice. [ABSTRACT FROM AUTHOR]

Graph theoretic problems are representative of fundamental kernels in traditional and emerging computational sciences such as chemistry, biology, and medicine, as well as applications in national security. Yet they pose serious challenges for parallel machines due to non-contiguous, concurrent accesses to global data structures with low degrees of locality. Few parallel graph algorithms outperform their best sequential implementation due to long memory latencies and high synchronization costs. In this talk, we consider several graph theoretic kernels for connectivity and centrality and discuss how the features of petascale architectures will affect algorithm development, ease of programming, performance, and scalability. [ABSTRACT FROM AUTHOR]

The Fast Fourier Transform (FFT) is of primary importance and a fundamental kernel in many computationally intensive scientific applications. In this paper we investigate its performance on the Sony-Toshiba-IBM Cell Broadband Engine, a heterogeneous multicore chip architected for intensive gaming applications and high performance computing. The Cell processor consists of a traditional microprocessor (called the PPE) that controls eight SIMD co-processing units called synergistic processor elements (SPEs). We exploit the architectural features of the Cell processor to design an efficient parallel implementation of Fast Fourier Transform (FFT). While there have been several attempts to develop a fast implementation of FFT on the Cell, none have been able to achieve high performance for input series with several thousand complex points. We use an iterative out-of-place approach to design our parallel implementation of FFT with 1K to 16K complex input samples and attain a single precision performance of 18.6 GFLOP/s on the Cell. Our implementation beats FFTW on Cell by several GFLOP/s for these input sizes and outperforms Intel Duo Core (Woodcrest) for inputs of greater than 2K samples. To our knowledge we have the fastest FFT for this range of complex inputs. [ABSTRACT FROM AUTHOR]

Betweenness is a centrality measure based on shortest paths, widely used in complex network analysis. It is computationally-expensive to exactly determine betweenness; currently the fastest-known algorithm by Brandes requires O(nm) time for unweighted graphs and O(nm + n2logn) time for weighted graphs, where n is the number of vertices and m is the number of edges in the network. These are also the worst-case time bounds for computing the betweenness score of a single vertex. In this paper, we present a novel approximation algorithm for computing betweenness centrality of a given vertex, for both weighted and unweighted graphs. Our approximation algorithm is based on an adaptive sampling technique that significantly reduces the number of single-source shortest path computations for vertices with high centrality. We conduct an extensive experimental study on real-world graph instances, and observe that our random sampling algorithm gives very good betweenness approximations for biological networks, road networks and web crawls. [ABSTRACT FROM AUTHOR]

Many large-scale optimization problems rely on graph theoretic solutions; yet high-performance computing has traditionally focused on regular applications with high degrees of locality. We describe our novel methodology for designing and implementing irregular parallel algorithms that attain significant performance on high-end computer systems. Our results for several fundamental graph theory problems are the first ever to achieve parallel speedups. Specifically, we have demonstrated for the first time that significant parallel speedups are attainable for arbitrary instances of a variety of graph problems and are developing a library of fundamental routines for discrete optimization (especially in computational biology) on shared-memory systems. Phylogenies derived from gene order data may prove crucial in answering some fundamental questions in biomolecular evolution. High-performance algorithm engineering offers a battery of tools that can reduce, sometimes spectacularly, the running time of existing approaches. We discuss one such such application, GRAPPA, that demonstrated over a billion-fold speedup in running time (on a variety of real and simulated datasets), by combining low-level algorithmic improvements, cache-aware programming, careful performance tuning, and massive parallelism. We show how these techniques are directly applicable to a large variety of problems in computational biology. [ABSTRACT FROM AUTHOR]

The developmental pattern of heart formation is highly conserved among all vertebrates. Lineage tracing studies of heart precursors in pregastrulating embryos have shown that the earliest identifiable presumptive cardiac cells are located on two patches lateral to the anterior-posterior axis of the epiblast (1-3). In the pregastrulation period, these cells migrate via ingression through to the primitive streak and position themselves within the primitive streak, later undergoing gastrulation to take up position in the antero-lateral mesoderm. These cells eventually become part of the lateral splanchnic mesoderm. The presumptive cardiac cells of the splanchnic mesoderm subsequently form a simple tube consisting of two layers—an inner endocardium and an outer myocardium—separated by a connective tissue-filled space called the cardiac jelly. The cardiac jelly is greatly expanded in the regions of the forming valves. [ABSTRACT FROM AUTHOR]

We consider the class of "left-looking" sequential matrix algorithms: consumer-driven algorithms that are characterized by "lazy" propagation of data. Left-looking algorithms are difficult to parallelize using the message-passing or distributed shared memory models because they only possess pipeline parallelism. We show that these algorithms can be directly parallelized using mobile pipelines provided by the Navigational Programming methodology. We present performance data demonstrating the effectiveness of our approach. [ABSTRACT FROM AUTHOR]

We consider the problem of estimating the location of a moving target in a 2-D plane. In this paper, we focus attention on selecting an appropriate 3rd sensor, given two sensors, with a view to minimize the estimation error. Only the selected sensors need to measure distance to the target and communicate the same to the central "tracker". This minimizes bandwidth and energy consumed in measurement and communication while achieving near minimum estimation error. In this paper, we have proposed that the 3rd sensor be selected based on three measures viz. (a) collinearity, (b) deviation from the ideal direction in which the sensor should be selected, and (c) proximity of the sensor from the target. We assume that the measurements are subject to multiplicative error. Further, we use least square error estimation technique to estimate the target location. Simulation results show that using the proposed algorithm it is possible to achieve near minimum error in target location. [ABSTRACT FROM AUTHOR]

Workstation clusters have high performance interconnects with programmable network processors, which facilitate interesting opportunities to offload certain application specific computation on them and hence enhance the performance of the parallel application. Our earlier work in this direction achieves enhanced performance and balanced utilization of resources by exploiting the programmable features of the network interface in parallel database query execution. In this paper, we extend our earlier work for studying parallel query execution with Bloom filters. We propose and evaluate a scheme to offload the Bloom filter operations to the network processor. Further we explore offloading certain tuple processing activities on to the network processor by adopting a network interface attached disk scheme. The above schemes yield a speedup of up to 1.13 over the base scheme with Bloom filter where all processing is done by the host processor and achieve balanced utilization of resources. In the presence of a disk buffer cache, which reduces both the disk and I/O traffic, offloading schemes improve the speedup to 1.24. [ABSTRACT FROM AUTHOR]

In cluster computing, InfiniBand has emerged as a popular high performance interconnect with MPI as the de facto programming model. However, even with InfiniBand, bandwidth can become a bottleneck for clusters executing communication intensive applications. Multi-rail cluster configurations with MPI-1 are being proposed to alleviate this problem. Recently, MPI-2 with support for one-sided communication is gaining significance. In this paper, we take the challenge of designing high performance MPI-2 one-sided communication on multi-rail InfiniBand clusters. We propose a unified MPI-2 design for different configurations of multi-rail networks (multiple ports, multiple HCAs and combinations). We present various issues associated with one-sided communication such as multiple synchronization messages, scheduling of RDMA (Read, Write) operations, ordering relaxation and discuss their implications on our design. Our performance results show that multi-rail networks can significantly improve MPI-2 one-sided communication performance. Using PCI-Express with two-ports, we can achieve a peak MPI_Put bidirectional bandwidth of 2620 Million Bytes/s, compared to 1910 MB/s for single-rail implementation. For PCI-X with two HCAs, we can almost double the throughput and reduce the latency to half for large messages. [ABSTRACT FROM AUTHOR]

IP-SAN and iSCSI are expected to remedy the problems of FC-based SAN. iSCSI has a structure of multilayer protocols. A typical configuration of the protocols to realize this system is as follows: SCSI over iSCSI over TCP/IP over Ethernet. Thus, in order to improve the performance of the system, it is necessary to precisely analyze the complicated behavior of each layer. In this paper, we present an IP-SAN analysis tool that monitors each of these layers from different viewpoints. By using this analysis tool, we experimentally demonstrate that the performance of iSCSI storage access can be significantly improved by more than 60 times. [ABSTRACT FROM AUTHOR]

Linear scan register allocation is an attractive register allocation algorithm because of its simplicity and fast running time. However, it is generally felt that linear scan register allocation yields poorer code than allocation schemes based on graph coloring. In this paper, we propose a pre-pass instruction scheduling algorithm that improves on the code quality of linear scan allocators. Our implementation in the Trimaran compiler-simulator infrastructure shows that our scheduler can reduce the number of active live ranges that the linear scan allocator has to deal with. As a result, fewer spills are needed and the quality of the generated code is improved. Furthermore, compared to the default scheduling and graph-coloring allocator schemes found in the IMPACT and Elcor components of Trimaran, our implementation with our pre-pass scheduler and linear scan register allocator significantly reduced compilation times. [ABSTRACT FROM AUTHOR]

Credential revocation is a critical problem in grid environments and remains unaddressed in existing grid security solutions. We present a novel grid authentication system that solves the revocation problem. It guarantees instantaneous revocation of both long-term digital identities of hosts/users and short-lived identities of user proxies. With our approach, revocation information is guaranteed to be fresh with high time-granularity. Our system employs mediated RSA (mRSA), adapts Boneh's notion of semi-trusted mediators to suit security in virtual organizations and propagates proxy revocation information as in Micali's NOVOMODO system. Our approach's added benefits include a configuration-free security model for end-users of the grid and fine-grained management of users' delegation capabilities. [ABSTRACT FROM AUTHOR]

This paper presents a new unified algorithm for cluster assignment and region scheduling, and its integration into an experimental retargetable code generation framework. The components of the framework are an instruction selector generator based on a recent technique, the IMPACT front end, a machine description module which uses a modification of the HMDES machine description language to include cluster information, a combined cluster allocator and an acyclic region scheduler, and a register allocator. Experiments have been carried out on the targeting of the tool to the Texas Instruments TMS320c62x architecture. We report preliminary results on a set of TI benchmarks. [ABSTRACT FROM AUTHOR]

In this paper, we consider the problem of scheduling divisible loads onto an heterogeneous star platform, with both heterogeneous computing and communication resources. We consider the case where the workers, after processing the tasks, send back some results to the master processor. This corresponds to a more general framework than the one used in many divisible load papers, where only forward communications are taken into account. To the best of our knowledge, this paper constitutes the first attempt to derive optimality results under this general framework (forward and backward communications, heterogeneous processing and communication resources). We prove that it is possible to derive the optimal solution both for LIFO and FIFO distribution schemes. Nevertheless, the complexity of the general problem remains open: we also show in the paper that the optimal distribution scheme may be neither LIFO nor FIFO. [ABSTRACT FROM AUTHOR]

A snap-stabilizing protocol, starting from any configuration, always behaves according to its specification. Here, we present the first snap-stabilizing protocol for arbitrary rooted networks which detects if a set of nodes is a cutset. This protocol is based on the depth-first search (DFS) traversal and its properties. One of the most interesting properties of our protocol is that, despite the initial configuration, as soon as the protocol is initiated by the root, the result obtained from the computations will be right. So, after the first execution of the protocol, the root is able to take a decision: "the input set is a cutset or not", and this decision is right. [ABSTRACT FROM AUTHOR]

We examine the problem of scheduling concurrent independent flows on multiple-disk I/O storage systems. Two models are considered: in the shared buffer model the memory buffer is shared among all the flows, while in the partitioned buffer model each flow has a private buffer. For the parallel disk model with d > 1 disks it is shown that the problem of minimizing the schedule length of n > 2 concurrent flows is NP-complete for both buffer models. A randomized scheduling algorithm for the partitioned buffer model is analyzed and probabilistic bounds on the schedule length are presented. Finally a heuristic based on static buffer allocation for the shared buffer model is discussed. [ABSTRACT FROM AUTHOR]

The use of traditional TCP, in its present form, for reliable transport over Ad hoc Wireless Networks (AWNs) leads to a significant degradation in the network performance. This is primarily due to the congestion window (cwnd) updation and congestion control mechanisms employed by TCP and its inability to distinguish congestion losses from wireless losses. In order to provide an efficient reliable transport over AWNs, we propose Learning-TCP, a novel learning automata based reliable transport protocol, which efficiently adjusts the cwnd size and thus reduces the packet losses. The key idea behind Learning-TCP is that, it dynamically adapts to the changing network conditions and appropriately updates the cwnd size by observing the arrival of acknowledgment (ACK) and duplicate ACK (DUPACK) packets. Learning-TCP, unlike other existing proposals for reliable transport over AWNs, does not require any explicit feedback, such as congestion and link failure notifications, from the network. We provide extensive simulation studies of Learning-TCP under varying network conditions, that show increased throughput (9-18%) and reduced packet loss (42-55%) compared to that of TCP. [ABSTRACT FROM AUTHOR]

Graph theoretic problems are representative of fundamental computations in traditional and emerging scientific disciplines like scientific computing and computational biology, as well as applications in national security. We present our design and implementation of a graph theory application that supports the kernels from the Scalable Synthetic Compact Applications (SSCA) benchmark suite, developed under the DARPA High Productivity Computing Systems (HPCS) program. This synthetic benchmark consists of four kernels that require irregular access to a large, directed, weighted multi-graph. We have developed a parallel implementation of this benchmark in C using the POSIX thread library for commodity symmetric multiprocessors (SMPs). In this paper, we primarily discuss the data layout choices and algorithmic design issues for each kernel, and also present execution time and benchmark validation results. [ABSTRACT FROM AUTHOR]

Multistage Interconnection Networks (MINs) provide the required switching infrastructure for many shared-memory multiprocessor systems and telecommunication networks. The concept of Supernetworks is evolving in response to emerging computation and communication intensive applications. Supernetworks exploit parallelism in both computing resources and communication infrastructures by interconnecting several computing clusters via high-bandwidth communication links. Wavelength Division Multiplexing (WDM) technology provides the communication infrastructure for Supernetowrks by dividing the bandwidth of a single fiber into numerous channels that can be used independently. In this paper, we investigate several architectures for WDM MINs that enhance the Supernetworks switching infrastructure. Our objective is to propose a new architecture and to evaluate its hardware complexity by comparing it to other WDM MINs architectures. [ABSTRACT FROM AUTHOR]

CPE-based IPsec VPNs have been widely used to provide secure private communication across the Internet. As the bandwidth of WAN links keeps growing, the bottleneck in a typical deployment of CPE-based IPsec VPNs has moved from the last-mile connections to the customer-edge security gateways. In this paper, we propose a clustering scheme to scale the throughput as required by CPE-based IPsec VPNs. The proposed scheme groups multiple security gateways into a cluster using a transparent self-dispatching technique and allows as many gateways to be added as necessary until the resulting throughput is again limited by the bandwidth of the last-mile connections. It also includes a flow-migration mechanism to keep the load of the gateways balanced. The results of the performance evaluation confirm that the clustering technique and the traffic-redistribution mechanism together create a transparent, adaptive, and highly scalable solution for building high-performance IPsec VPNs. [ABSTRACT FROM AUTHOR]

We present an output-queued switch architecture with cross-point buffering that has improved performance for both point-to-point communication and hardware accelerated collective communication. In the past, output queuing architectures have been less popular as they require more internal speedup and buffering. However, with current technology it is possible to build output-queued switches with a relatively large number of ports. We demonstrate that our output-queued architecture performs well for point-to-point messages, specially in a fat-tree topology. We also show that output-queued architectures facilitate efficient implementations of multicasts and reductions. We present performance of multicasts and reductions on individual switches and a network of switches interconnected in a fat-tree topology. We also present simulation results based on synthetic workloads that emulate a molecular dynamics application. [ABSTRACT FROM AUTHOR]

This paper proposes a novel low-power 32bit×32bit multiplier with pipelined block-wise shutdown scheme. When it idles, it turns off supply voltage to reduce both dynamic and static power. It shutdowns and wakes up sequentially along with pipeline stage to avoid power line noise. In idle mode, the proposed multiplier consumes 0.013mW and 0.006mW in 0.13μm and 0.09μm technologies, respectively, and it reduces power consumption to 0.07%~0.08% of active mode. As fabrication technology becomes small, power efficiency degrades in the conventional clock gating scheme, but the proposed multiplier does not. The low-power design methodology in this paper can be easily adopted in most functional blocks with pipeline architecture. [ABSTRACT FROM AUTHOR]

The performance of user-level messaging in PIM (Processing-In-Memory) to PIM communication is modeled and analyzed for the DIVA (Data IntensiVe Architecture) system. Six benchmarks have been used for this purpose, two from each category, namely single message transfer, parallel transfer and collective communication, as described for the PMB (Pallas MPI Benchmarks). The benchmarks used are PingPong, PingPing, SendReceive, Exchange, Barrier synchronization and AllToAll personalized exchange. The main significance of this work lies in the evaluation of an implementation of system-wide support for memory-to-memory and memory-to-host communi-cation via a parcel buffer (used as a network interface). Another remarkable feature of this evaluation lies in presenting an optimal algorithm for Barrier synchronization and an optimal algorithm, with full channel utilization, for AllToAll personalized exchange for the bi-directional ring configuration of up to 8 DIVA PIMs in the memory system of a Hewlett-Packard's zx6000 server. The algorithms presented can be scaled for higher number of PIM chips with a little degradation in performance over the optimal solution. Our analysis shows that the currently employed communication mechanism can be used very efficiently for collective communication operations, and it also exposes the bottlenecks in the current design for future improvements. [ABSTRACT FROM AUTHOR]

We explore the opportunities offered by current and forthcoming VLSI technologies to on-chip multiprocessing for Quantum Chromo Dynamics (QCD), a computational grand challenge for which over half a dozen specialized machines have been developed over the last two decades. Based on a careful study of the information exchange requirements of QCD both across the network and within the memory system, we derive the optimal partition of die area between storage and functional units. We show that a scalable chip organization holds the promise to deliver from hundreds to thousands flop per cycle as VLSI feature size scales down from 90 nm to 20 nm, over the next dozen years. [ABSTRACT FROM AUTHOR]

Data dependencies between instructions have traditionally limited the ability of processors to execute instructions in parallel. Data value predictors are used to overcome these dependencies by guessing the outcomes of instructions. Because mispredictions can result in a significant performance decrease, most data value predictors include a confidence estimator that indicates whether a prediction should be used. This paper presents a global approach to confidence estimation in which the prediction accuracy of previous instructions is used to estimate the confidence of the current prediction. Perceptrons are used to identify which past instructions affect the accuracy of a prediction and to decide whether the prediction is likely to be correct. Simulation studies compare this global confidence estimator to the more conventional local confidence estimator. Results show that predictors using this global confidence estimator tend to predict significantly more instructions and incur fewer mispredictions than predictors using existing local confidence estimation approaches. [ABSTRACT FROM AUTHOR]

We describe the analysis of an on-line pattern-recognition algorithm to dynamically control the configuration of the L1 data cache of a high-performance processor. The microarchitecture achieves higher performance and energy saving due to the accommodation of operating frequency, capacity, set-associativity, line size, hit latency, energy per access, and chip area to program workload and ILP. We show that for the operating frequency 4.5 GHz, the execution time is always reduced with an average measure of 12.1% when compared to a non-adaptive high-performance processor. Additionally, the energy saving is 2.7% on average, and t1he product time-energy is reduced on average by 14.9%. We also consider a profile-based reconfiguration of data cache, which allows picking different cache configurations but only one can be chosen for each program. Experimental results indicate that this approach yields a high percentage of the performance improvement and energy saving achieved by the on-line algorithm. [ABSTRACT FROM AUTHOR]

Wireless Sensor Networks (WSNs) consist of a large number of nodes networked via wireless links. In many WSN settings, sensor nodes are deployed in an ad hoc manner. One important issue in this context is to detect the boundary of the deployed network to ensure that the sensor nodes cover the target area. In this paper, we propose a new algorithm that can be used to discover the boundary of a randomly deployed WSN. The algorithm does not require the sensor nodes to be equipped with positioning devices and is scalable for large number of nodes. Simulation experiments are developed to evaluate the performance of the proposed algorithms for different network topologies. The simulation results show that the algorithm detects the boundary nodes of the network with high accuracy. [ABSTRACT FROM AUTHOR]

Current superscalar architectures inherently depend on an instruction issue queue to achieve multiple instruction issue and out-of-order execution. However, the issue queue is implemented as a centralized structure and mainly causes globally broadcasting operations to wake up and select the instructions. Therefore, a large issue queue ultimately results in a low clock rate along with a high circuit complexity. This paper proposes Speculative Pre-Execution Assisted by compileR (SPEAR), a low-complexity issue queue design. SPEAR is designed to manage the small issue queue more efficiently without increasing the queue size. To this end, we have first recognized that the long memory latency is one of the factors which demand a large queue, and we aim at achieving early execution of the miss-causing load instructions using another hierarchy of an issue queue. We speculatively pre-execute those miss-causing instructions as an additional prefetching thread. [ABSTRACT FROM AUTHOR]

Time synchronization is an important aspect of distributed computer systems and networks. Nodes must be synchronized to a common clock to determine slot durations for a TDMA based transmission scheme. Most efficient slot-assignment algorithms apportion the TDMA slots with the underlying assumption of a reasonably accurate global synchronization of the network. In this paper, we propose a novel synchronization protocol for ad hoc, sensor, and other dense multi-hop infrastructure-less wireless networks. The protocol performs a random leader election to achieve global network synchronization. We have analyzed the variation of synchronization time and error with different node densities and mobility speeds, by simulating the protocol. Expressions have been derived reflecting the worst case synchronization error, and the maximum synchronization time, for a network with uniform distribution of nodes. Simulation results show that out-of-band and piggybacked signaling have good accuracy of synchronization, and that a considerable bandwidth saving occurs with piggybacking on data or acknowledgment packets. [ABSTRACT FROM AUTHOR]

With the emergence of powerful processors and complex applications, wireless communication devices are increasingly power hungry. While there exist several solutions to provide transmission power management in cellular wireless networks and ad hoc wireless networks, it remains an open problem in recently proposed hybrid wireless networks. The Multihop Cellular Network (MCN) and Multi Power Architecture for Cellular network (MuPAC) are instances of hybrid wireless networks, which are proposed to increase the system throughput and spectrum reuse by infusing multihop radio relaying mechanism into the infrastructure-based wireless networks. This paper proposes a novel variable power optimization scheme for the hybrid wireless network architectures such as MCN and MuPAC in order to optimize the power consumption at a mobile node without losing the throughput advantage gained by the multihop scheme. Extensive simulation results show 10% to 15% improvement in power consumption and system throughput which is significant in case of power constrained mobile nodes. [ABSTRACT FROM AUTHOR]

Wireless Sensor Networks (WSNs) possess highly con- strained energy resources. The existing Medium Access Control (MAC) protocols for WSNs try to either minimize the energy consumption or the latency, which are conflicting objectives, or find a trade-off between them. They fail to achieve the minimum energy × latency, which ensures that transmission should occur such that both the energy consumption and latency are minimized. We propose a novel Battery-aware Energy-efficient MAC protocol to minimize the Latency (BEL-MAC) that exploits the chemical properties of the batteries of the sensor nodes, in order to increase their lifetime. Our protocol reduces the latency of the packets in an efficient manner without compromising on the lifetime of the network. We compare our protocol with the SMAC, DSMAC, TMAC, and IEEE 802.11 MAC, in terms of throughput and latency and show that our protocol outperforms these existing protocols, in terms of energy × latency. [ABSTRACT FROM AUTHOR]

Complexity of parallel application development has been one of the major obstacles towards the mainstream adoption of parallel programming. In order to hide some of these complexities, researchers have been actively investigating the pattern-based approaches to parallel programming. As reusable components, patterns are intended to ease the design and development phases of parallel applications. Parallel Architectural Skeleton (PAS) is one such pattern-based parallel programming model which describes the architectural aspects of parallel patterns. Like many other pattern-based parallel programming models and tools, the benefits of PAS were offset by the difficulties in extending PAS. EPAS is an extension of PAS that addresses this issue. Using EPAS, a skeleton designer can design new skeletons and add them to the skeleton repository (i.e., extensibility). EPAS also makes the PAS model more flexible by defining composition of skeletons. In this paper, we describe the model of EPAS and also discuss some of the recent usability and performance studies. The studies demonstrate that EPAS is a practical and usable parallel programming model and tool. [ABSTRACT FROM AUTHOR]

A minimum connected dominating set is an efficient approach to form a virtual backbone for ad-hoc networks. We propose a tree based distributed time/message efficient approximation algorithm to compute a small connected dominating set without using geographic positions. The algorithm has O(n) time, O(n log n) message complexity, and has an approximation factor of eight. The algorithm is implemented using dominating set simulation program, which shows that our method gives smaller connected dominating set than the existing methods. Keywords: independent set, connected dominating set, MANET. [ABSTRACT FROM AUTHOR]

The performance of parallel applications running on large clusters is known to degrade due to the interference of kernel and daemon activities on individual nodes, often referred to as noise. In this paper, we focus on an important class of parallel applications, which repeatedly perform computation, followed by a collective operation such as a barrier. We model this theoretically and demonstrate, in a rigorous way, the effect of noise on the scalability of such applications. We study three natural and important classes of noise distributions: The exponential distribution, the heavy-tailed distribution, and the Bernoulli distribution. We show that the systems scale well in the presence of exponential noise, but the performance goes down drastically in the presence of heavy-tailed or Bernoulli noise. [ABSTRACT FROM AUTHOR]

In this paper we describe the design and implementation of a C++ based Common Component Architecture (CCA) framework, XCAT-C++. It can efficiently marshal and unmarshal large data sets, and provides the necessary modules and hooks in the framework to meet the requirements of distributed scientific applications. XCAT-C++ uses a high-performance multi-protocol library so that the appropriate communication protocol is employed for each pair of interacting components. Scientific applications can dynamically switch to a suitable communication protocol to maximize effective throughput. XCAT-C++ component layering imposes minimal overhead and application components can achieve highly efficient throughput for large data sets commonly used in scientific computing. It has a suite of tools to aid application developers including a flexible code generation toolkit and a python scripting interface. XCAT-C++ provides the means for application developers to leverage the efficacy of the CCA component model to manage the complexity of their distributed scientific simulations. Keywords: CCA, XCAT-C++, component, performance, multi-protocol. [ABSTRACT FROM AUTHOR]

Effective data distribution and parallelization of computations involving irregular data structures is a challenging task. We address the twin-problems in the context of computations involving block-sparse matrices. The programming model provides a global view of a distributed block-sparse matrix. Abstractions are provided for the user to express the parallel tasks in the computation. The tasks are mapped onto processors to ensure load balance and locality. The abstractions are based on the Aggregate Remote Memory Copy Interface, and are interoperable with the Global Arrays programming suite and MPI. Results are presented that demonstrate the utility of the approach. [ABSTRACT FROM AUTHOR]

The dynamism and space-time heterogeneity exhibited by structured adaptive mesh refinement (SAMR) applications makes their scalable parallel implementation a significant challenge. This paper investigates an adaptive hierarchical multi-partitioner (AHMP) framework that dynamically applies multiple partitioners to different regions of the domain, in a hierarchical manner, to match the local requirements of these regions. Key components of the AHMP framework include a segmentation-based clustering algorithm (SBC) for identifying regions in the domain with relatively homogeneous partitioning requirements, mechanisms for characterizing the partitioning requirements, and a runtime system for selecting, configuring and applying the most appropriate partitioner to each region. The AHMP framework has been implemented and experimentally evaluated on up to 1280 processors of the IBM SP4 cluster at San Diego Supercomputer Center. Keywords: Parallel Computing, Adaptive Mesh Refinement, Dynamic Load Balancing, Hierarchical Multi-Partitioner. [ABSTRACT FROM AUTHOR]

JavaSymphony is a high-level programming model for performance oriented distributed and parallel Java applications, which allows the programmer to control parallelism, load balancing, and locality at a high level of abstraction. In this paper, we describe an extension of JavaSymphony that deals with distributed workflow applications as graphs of software components, which can be executed on a distributed set computers. Workflows are not limited to DAGs, but also cover complex control flow including loops. Furthermore, we introduce a novel approach for workflow scheduling based on the HEFT algorithm and resource brokerage for a heterogeneous set of computers. We demonstrate the effectiveness of our approach with two real-world applications and compare our techniques against the widely known DAGMan Condor scheduler. [ABSTRACT FROM AUTHOR]

Traditionally graphics clusters have been employed in real-time visualization of large geometric models (many millions of 3D points). Data parallel approaches have been the obvious choices when it comes to breaking up the computations over multiple processors. In recent years, programmable graphics hardware has gained widespread acceptance. Today, every processing node in a graphics cluster has two powerful and fully programmable processors - a CPU (Central Processing Unit) and a GPU (Graphics processing unit). It enables distribution of graphics computations targeting an applications's needs in more flexible ways. In this paper we discuss and analyze our implementation of functionality distributed point-based rendering pipeline with impressive performance improvements. To the best of our knowledge, it is the first attempt to devise a functionality distribution scheme for a large data and compute-intensive application. We discuss the merits and limitations of such a distribution scheme by comparing it against traditional data parallel and single node schemes. [ABSTRACT FROM AUTHOR]

In this paper, we present a novel intra-task Dynamic Voltage Scheduling (DVS) algorithm based on the knowledge of frequently executed paths in the control flow graph for real-time embedded systems. The basic idea is to construct a common path composing all the frequently executed paths (hot-paths) and perform DVS scheduling based on this common path, rather than the most probable path. We compare the performance (energy consumption) of our algorithm with a recently proposed algorithm. Our simulation results show that the proposed algorithm performs better than the existing algorithm for most of the simulated conditions. We also identify interesting research problems in this context. [ABSTRACT FROM AUTHOR]

A new parallel algorithm to compute Euclidean metric-based Hausdorff distance measures between binary images (typically edge maps) is proposed in this paper. The algorithm has a running time of O(n) for images of size n × n. Further, the algorithm has the following features: (i) simple arithmetic (ii) identical computations at each pixel and (iii) computations using a small neighborhood for each pixel. An efficient cellular architecture for implementing the proposed algorithm is presented. Results of implementation using field-programmable gate arrays show that the measures can be computed for approximately 88000 image pairs of size 128×128 in a second. This result is valuable for real-time applications like object tracking and video surveillance. [ABSTRACT FROM AUTHOR]