In this paper, we propose micROS.BT, an event-driven behavior tree (BT) framework aiming at supporting swarm-robot coordination. Compared with other BT frame-works, micROS.BT implements the event-driven way under the multi-thread mode, which can effectively save computing resources. Moreover, in order to ensure swarm-robot coordination, we optimize the implementation of the traditional blackboard and propose the multi-mode blackboard, which supports inner-tree, inter-tree, and inter-robot data sharing. Furthermore, considering the limited modularity of a single tree, micROS.BT realizes a mechanism called hierarchical tree management which involves inter-tree notifying and waiting functionalities, while ensuring that each tree is independent and self-scheduled. The effectiveness of micROS.BT is verified by simulation and real-robot experiments for different system settings, showing that a substantial improvement is achieved in comparison with the traditional BT implementations.

Programming cooperative tasks for autonomous swarm robotic systems has always been challenging. In this paper, we introduce a concept `Actor', as a virtualization for robot platforms. Every robot platform in the swarm robotic system carries out the task and interacts with others as an Actor. We designed an Actor-based framework for the management of autonomous swarm robotic systems including modules and interfaces for the Actor, the collective Actor, and task management. The Actor-based framework enables task developers to explicitly model cooperative tasks without intricacies about the detailed robotic algorithms or the specific robot brands, and eases the burden on robotic algorithm developers by providing common functionalities. The proposed framework is implemented in C++ and validated quantitatively and qualitatively with a swarm of thirty drones by simulations and a swarm of ten drones by in-field tests.

Summary For parallel multiphase flows, the core procedure is solving linear systems using preconditioned iterative methods, and the iterative convergence rate is crucial to the overall efficiency. How the mesh is partitioned influences the iterative convergence rate. However, the numerical characteristics of the linear systems vary significantly along with the time steps because of the dramatic change of the flow fields. Traditional static mesh partition cannot guarantee a good convergence feature throughout the simulation. A dynamic mesh re‐partitioning scheme MDMRPar (Multiphase Dynamic Mesh Re‐Partitioning) is proposed and implemented in OpenFOAM (Open Field Operation And Manipulation). MDMRPar employs a new surface field to record the linear system information in every time step. For simple multiphase problems with topo‐invariant mesh, MDMRPar periodically adopts the numerical information from the previous time step and calculates a weighted graph from the mesh topology in a straightforward way. For multiphase flows using adaptive mesh refinement method, a coarse graph with vertex weights is built based on the mesh topology and refinement history. The numerical information on the surface field is integrated into the coarse graph as edge weights. In both cases, weighted graphs are re‐partitioned by ParMetis, a general multi‐level parallel graph re‐partitioning package. Experimental results on three multiphase flows show that MDMRPar significantly outperforms the traditional partitioning/re‐partitioning schemes both in the iterative convergence rate and the total simulation time.

Abstract Multirobot systems have been studied extensively in the recent years. Maintaining connectivity has significant impacts on the stability and convergence of the multirobot systems. In this work, we design a three‐layer framework for multirobot coordination. Furthermore, a novel distributed algorithm is proposed to achieve the navigation objective while satisfying connectivity maintenance and collision avoidance constraints. The algorithm is a hybrid of an rapidly exploring random tree‐based planner and an extended distributed navigation function‐based controller. The coordination framework and the distributed algorithm are demonstrated to be effective through a series of illustrative simulations. They outperform the current state‐of‐the‐art method in terms of efficiency and applicability.

Subsequent to publication, the affiliation and citation of the article by Huang et al.1 have been modified. The correct order is presented above.

In this paper, we consider a surveillance scenario where a team of sensing robots survey a sensitive area and transmit the monitored data to a remote base station through a mobile relay. In this scenario, it is challenging to autonomously adjust the position of the mobile relay for the sake of minimizing the total communication-motion energy consumption of the system, while maintaining the communication quality of the mobile sensing robots. We first derive the asymptotically optimal transmit powers of the mobile relay and of the sensing robots according to the predefined end-to-end packet error rate (PER) requirement. Then, we propose a joint communication-motion planning (JCMP) method for minimizing the total communication-motion energy consumption in both: single- and multi-sensing-robot scenarios, where the trajectories of the sensing robots are rigorously defined. We further consider the scenario where the sensing robots' trajectories are not fixed but can be optimized in restrained areas. The effectiveness of the proposed JCMP is verified by analysis and numerical results for different system configurations, showing that a substantial energy-efficiency improvement may be achieved in comparison with the benchmark that only optimizes the communication energy consumption.

Abstract In this paper, we propose a distributed control approach for flocking and group maneuvering of nonholonomic agents, with constrained kinematic properties commonly found in practical systems, such as fixed‐wing unmanned aerial vehicles. Flocking of agents with differential drive kinematics is addressed by introducing a virtual leader–follower mechanism into the Olfati‐Saber's algorithm, which is originally proposed for holonomic agents with double integrator kinematics. Then, group maneuverability of the flock is achieved by superimposing a group motion onto each agent's flocking motion. Moreover, it is proven that speed limits are intrinsically guaranteed by the approach, which renders it more applicable in practical systems. Experimental results in MATLAB and Gazebo, a popular robotic simulator, are presented to evaluate the performance and demonstrate the effectiveness of the proposed approach.

Disease gene identification is a key step to understand the cellular mechanisms associated with a specific disease. Compared with biological experiments, computational predictions of disease genes are cheaper and more effortless. Many computational methods are used to detect causal genes for diseases on the protein-protein interaction (PPI) networks generated by the high-throughput technology. However, the accuracy of these methods need to be improved due to the false interactions in the PPI data. To deal with the challenge, other methods are proposed via the integration of biological information from different sources with the PPI networks. In this work, a new algorithm AIDG is developed to predict disease genes. First, the weighted PPI networks are built by incorporating the protein subcellular localization information into the human PPI networks. Next, all of disease candidate genes are scored in terms of a iteration function. Finally, they are ranked on descending order of their scores. The top candidates are considered as potential disease genes. The results from the leave-one-out crossing validation (LOOCV) show that AIDG outperforms other similar methods like DADA and ToppNet.

The method of Brownian configuration fields (BCF) is a promising multi-scale approach for the simulationof viscoelastic fluids, however, it is a computationally expensive method, which restricts its application in complex scenarios. Therefore, it is of great importance to optimize the parallel implementation in order to improve computational efficiency. In this paper we propose a hybrid decomposition parallel algorithm named: MCDPar, whichenables the simulation problem to bedecomposed simultaneously over mesh cells andthe Brownian configuration fields. Compution processes are split into multiple groups and Brownian configuration fields are equally associated with these groups. Meanwhile, within each group the processes are concurrently executed based on the traditional mesh decomposition approach. Finally we implemented the MCDPar algorithm in a micro-macro numerical solver based on OpenFOAM. Experimental results show that the micro-macro simulation time of viscoelastic fluids issignificantly reduced with improved scalability and parallel efficiency. In the test case with Nf= 2000 and Ncell= 262144, the speedup of the MCDParis up to 9.23x with a 7.5x increase in number of cores compared to the original parallel algorithm.

Abstract This paper proposes an efficient and stable numerical method for modeling catheterization during endovascular surgeries. The guidewire‐catheter combination is treated as an elastic rod, which has very large resistance against twisting about its medial axis. A torsion free assumption is made, and the physical behavior of the rod is predominately governed by stretching and bending energies. This simplification greatly reduces the computational complexity and makes the model more stable, while the simulation results are still realistic enough for its application in endovascular surgeries. A contact handling algorithm that directly makes use of the volume data of the relevant tissues is proposed to simulate the interaction between the guidewire‐catheter combination and the aortic wall. During each simulation step, the penetration depth of each vertex in contact with the aortic wall is calculated using moving least squares surfaces, and the contact is then resolved in a position‐based manner. A comprehensive quantitative evaluation of the rod model is performed to validate its accuracy. Finally, the proposed approach is applied in a prototype system for simulation of endovascular aneurysm repair surgeries. Its efficiency and effectiveness are demonstrated in a real‐time interactive catheterization simulation. Copyright © 2016 John Wiley & Sons, Ltd.

Abstract This paper presents an interactive simulation system for surgical procedures of endovascular aneurysm repair. It extracts anatomical structure of clinic interest from patient‐specific X‐ray computed tomography or magnetic resonance imaging data by image segmentation techniques, and then reconstructs surface triangular meshes of these anatomical structures from the volumetric data. The core of the system is an interactive computer‐based simulation module. It consists of a physical modeling unit, a collision detection unit, a visualization unit, and a control unit. The integration of these units together makes it possible for users to interact with the system in real time, performing virtual catheterization, angiography, and stent graft deployment under a user‐specified rendering mode. The prototype system can be used as a cost‐efficient tool for surgical planning with patient‐specific anatomical geometry and for practice of surgical procedures before actual operation. Copyright © 2016 John Wiley & Sons, Ltd.

This paper formulates multi-label learning as a constrained projective non-negative matrix factorization (CPNMF) problem which concentrates on a variant of the original projective NMF (PNMF) and explicitly introduces an auxiliary basis to learn the semantic subspace and boosts its discriminating ability by exploiting labeled and unlabeled examples together. Particularly, it propagates labels of the labeled examples to the unlabeled ones by enforcing coefficients of examples sharing identical semantic contents to be identical based on a hard constraint, i.e., embedding the class indicator of labeled examples into their coefficients. CPNMF preserves the geometrical structure of dataset via manifold regularization meanwhile captures the inherent structure of labels by using label correlations. We developed a multiplicative update rule (MUR) based algorithm to optimize CPNMF and proved its convergence. Experiments of image annotation on Corel dataset, text categorization on Rcv1v2 dataset, and text clustering on two popular text corpuses suggest the effectiveness of CPNMF.

Regarding the non-negativity property of the magnitude spectrogram of speech signals, nonnegative matrix factorization (NMF) has obtained promising performance for speech separation by independently learning a dictionary on the speech signals of each known speaker. However, traditional NM-F fails to represent the mixture signals accurately because the dictionaries for speakers are learned in the absence of mixture signals. In this paper, we propose a new transductive NMF algorithm (TNMF) to jointly learn a dictionary on both speech signals of each speaker and the mixture signals to be separated. Since TNMF learns a more descriptive dictionary by encoding the mixture signals than that learned by NMF, it significantly boosts the separation performance. Experiments results on a popular TIMIT dataset show that the proposed TNMF-based methods outperform traditional NMF-based methods for separating the monophonic mixtures of speech signals of known speakers.

To report a compiler bug, one must often find a small test case that triggers the bug. The existing approach to automated test-case reduction, delta debugging, works by removing substrings of the original input; the result is a concatenation of substrings that delta cannot remove. We have found this approach less than ideal for reducing C programs because it typically yields test cases that are too large or even invalid (relying on undefined behavior). To obtain small and valid test cases consistently, we designed and implemented three new, domain-specific test-case reducers. The best of these is based on a novel framework in which a generic fixpoint computation invokes modular transformations that perform reduction operations. This reducer produces outputs that are, on average, more than 25 times smaller than those produced by our other reducers or by the existing reducer that is most commonly used by compiler developers. We conclude that effective program reduction requires more than straightforward delta debugging.

The stream processors represent a promising alternative to traditional cache-based general-purpose processors in achieving high performance in stream applications (media and some scientific applications). In a stream programming model for stream processors, an application is decomposed into a sequence of kernels operating on streams of data. During the execution of a kernel on a stream processor, all streams accessed must be communicated through a nonbypassing software-managed on-chip memory, the SRF (Stream Register File). Optimizing utilization of the scarce on-chip memory is crucial for good performance. The key insight is that the interference graphs (IGs) formed by the streams in stream applications tend to be comparability graphs or decomposable into a set of comparability graphs. We present a compiler algorithm for finding optimal or near-optimal colorings, that is, SRF allocations in stream IGs, by computing a maximum spanning forest of the sub-IG formed by long live ranges, if necessary. Our experimental results validate the optimality and near-optimality of our algorithm by comparing it with an ILP solver, and show that our algorithm yields improved SRF utilization over the First-Fit bin-packing algorithm, the best in the literature.

Reliability is a key challenge to be understood to turn the vision of exascale supercomputing into reality. Inevitably, large-scale supercomputing systems, especially those at the peta/exascale levels, must tolerate failures, by incorporating fault-tolerance mechanisms to improve their reliability and availability. As the benefits of fault-tolerance mechanisms rarely come without associated time and/or capital costs, reliability will limit the scalability of parallel applications. This paper introduces for the first time the concept of "Reliability Wall” to highlight the significance of achieving scalable performance in peta/exascale supercomputing with fault tolerance. We quantify the effects of reliability on scalability, by proposing a reliability speedup, defining quantitatively the reliability wall, giving an existence theorem for the reliability wall, and categorizing a given system according to the time overhead incurred by fault tolerance. We also generalize these results into a general reliability speedup/wall framework by considering not only speedup but also costup. We analyze and extrapolate the existence of the reliability wall using two representative supercomputers, Intrepid and ASCI White, both employing checkpointing for fault tolerance, and have also studied the general reliability wall using Intrepid. These case studies provide insights on how to mitigate reliability-wall effects in system design and through hardware/software optimizations in peta/exascale supercomputing.

Using the graphics processing unit (GPU) to accelerate the general purpose computation has attracted much attention from both the academia and industry due to GPU's powerful computing capacity. Thus optimization of GPU programs has become a popular research direction. In order to support the general purpose computing more efficiently, GPU has integrated the general data cache to replace the existing software-managed on-chip memory. Consequently, improving the usage of the data cache becomes of vital importance to improve the performance of the GPU programs. The foundation of cache locality optimizations is efficient analysis and prediction of the cache behavior. Unfortunately, existing cache miss analysis models are based on sequential programs and thus cannot be used to analyze the GPU programs directly. In this paper, based on the deep analysis of GPU's execution model, we propose, for the first time, a cache miss analysis model for the GPU programs. We divide the problem into two subproblems: stack distance profile analysis of single thread block and cache contention analysis of multiple thread blocks. The experimental results from nine typical application kernels in the scientific computing field illustrate that our method is efficient and can be used to guide the cache locality optimizations for the GPU programs.

Compilers should be correct. To improve the quality of C compilers, we created Csmith, a randomized test-case generation tool, and spent three years using it to find compiler bugs. During this period we reported more than 325 previously unknown bugs to compiler developers. Every compiler we tested was found to crash and also to silently generate wrong code when presented with valid input. In this paper we present our compiler-testing tool and the results of our bug-hunting study. Our first contribution is to advance the state of the art in compiler testing. Unlike previous tools, Csmith generates programs that cover a large subset of C while avoiding the undefined and unspecified behaviors that would destroy its ability to automatically find wrong-code bugs. Our second contribution is a collection of qualitative and quantitative results about the bugs we have found in open-source C compilers.

Existing scratchpad memory (SPM) allocation algorithms for arrays, whether they rely on well-crafted heuristics or resort to integer linear programming (ILP) techniques, typically assume that every array is small enough to fit directly into the SPM. As a result, some arrays have to be spilled entirely to the off-chip memory in order to make room for other arrays to stay in the SPM, resulting in sometimes poor SPM utilization.

This paper presents reuse-aware modulo scheduling to maximizing stream reuse and improving concurrency for stream-level loops running on stream processors. The novelty lies in the development of a new representation for an unrolled and software-pipelined stream-level loop using a set of reuse equations, resulting in simultaneous optimization of two performance objectives for the loop, reuse and concurrency, in a unified framework. We have implemented this work in the compiler developed for our 64-bit FT64 stream processor. Our experimental results obtained on FT64 and by simulation using nine representative stream applications demonstrate the effectiveness of the proposed approach.

Model abstraction plays an important role in model checking of source codes of programs. Slicing execution is a lightweight symbolic execution procedure to extract the models of C programs in an over-approximated way. In this paper, we present an approach to improving slicing execution with a novel concept called partial weakest precondition (PWP) to alleviate the space explosion problem. PWPs specify the corresponding weakest precondition conservatively by only considering part of program variables. We present how to integrate PWP with slicing execution, which leads to a compact model with much smaller state space compared with the one obtained by the original slicing execution. A new PWP implementation is also presented to avoid possible exponential PWP formula size and support pointers and aliases as well. The distinguished features of the implementation are that it does not need to translate the program to the passive form beforehand, and it supports loops very well. Comparing with slicing execution without PWP, the experimentation on SSL protocol based on the C source code openssl-0.9.6c shows that the state space may be reduced to only 1/10 after applying PWP.

Memory accesses limit the performance of stream processors. By exploiting the reuse of data held in the Stream Register File (SRF), an on-chip, software controlled storage, the number of memory accesses can be reduced. In current stream compilers, reuse exploitation is only attempted for simple stream references, those whose start and end are known. Compiler analysis, from outside of stream processors, does not directly enable the consideration of other more complex stream references. In this article, we propose a transformation to automatically optimize stream programs to exploit the reuse supplied by loop-dependent stream references. The transformation is based on three results: lemmas identifying the reuse supplied by stream references, a new abstract representation called the Stream Reuse Graph (SRG) depicting the identified reuse, and the optimization of the SRG for our transformation. Both the reuse between the whole sequences accessed by stream references and between partial sequences is exploited in the article. In particular, partial reuse and its treatment are quite new and have never, to the best of our knowledge, appeared in scalar and vector processing. At the same time, reusing streams increases the pressure on the SRF, and this presents a problem of which reuse should be exploited within limited SRF capacity. We extend our analysis to achieve this objective. Finally, we implement our techniques based on the StreamC/KernelC compiler that has been optimized with the best existing compilation techniques for stream processors. Experimental results show a resultant speed-up of 1.14 to 2.54 times using a range of benchmarks.

Load balancing is an important problem for parallel applications. Recently, many super computers are built on multi-core processors which are usually sharing the last level cache. On one hand different accesses from different cores conflict each other, on the other hand different cores have different work loads resulting in load unbalancing. In this paper, we present a novel technique for balancing parallel applications for multi-core processors based on cache partitioning which can allocate different part of shared caches to different cores exclusively. Our intuitive idea is partitioning shared cache to different cores based on their workloads. That is to say, a heavy load core will get more shared caches than a light load core, so the heavy load core runs faster. We give 2 algorithms in this paper, initial cache partitioning algorithm (ICP) and dynamical cache partitioning algorithm (DCP). ICP is used to determine the best partition when application starting while DCP is used to adjust the initial partition based on the changes of load balancing. Our experiment results show that the running time can be reduced by 7% on average when our load balancing mechanism based on cache partitioning is used.

Graphic Processing Unit (GPU), with many light-weight data-parallel cores, can provide substantial parallel computational power to accelerate general purpose applications. But the powerful computing capacity could not be fully utilized for memory-intensive applications, which are limited by off-chip memory bandwidth and latency. Stencil computation has abundant parallelism and low computational intensity which make it a useful architectural evaluation benchmark. In this paper, we propose some memory optimizations for a stencil based application mgrid from SPEC 2K benchmarks. Through exploiting data locality in 3-level memory hierarchies and tuning the thread granularity, we reduce the pressure on the off-chip memory bandwidth. To hide the long off-chip memory access latency, we further prefetch data during computation through double-buffer. In order to fully exploit the CPU-GPU heterogeneous system, we redistribute the computation between these two computing resource. Through all these optimizations, we gain 24.2x speedup compared to the simple mapping version, and get as high as 34.3x speedup when compared with a CPU implementation.

Most programming languages support a call stack in the programming model and also in the runtime system.We show that for applications targeting low-power embedded microcontrollers (MCUs), RAM usage can be significantly decreased by partially or completely eliminating the runtime callstack. We present flattening, a transformation that absorbs a function into its caller, replacing function invocations and returns with jumps. Unlike inlining, flattening does not duplicate the bodies of functions that have multiple callsites. Applied aggressively, flattening results in stack elimination. Flattening is most useful in conjunction with a lifting transformation that moves global variables into a local scope.

In a chip-multiprocessor with a shared cache structure, the last level cache is shared by multiple applications executing simultaneously. The competing accesses from different applications degrade the system performance, resulting in non-predicting executing time. Cache partitioning techniques partition the shared cache for multiple applications. Traditional cache partitioning mechanisms, such as Utility-based Cache Partitioning (UCP) and IPC-based Cache Partitioning (IPC-CP), aim to optimize the objective (for example, instruction per cycle or miss rate) that is appealing for individual application. However, the performances of multi-programmed systems are usually characterized by the number of applications finished during certain interval. This paper investigates System Level Speedup oriented Cache Partitioning (SLS-CP), which is used to maximize total speedup of the system. Like UCP and IPC-CP, the inputs of SLS-CP are current performance status and misses of all the possible partitions, and the outputs of SLS-CP are optimum cache partitions for multi-programmed workloads. Our evaluation, on top of a two cores CMP processor with 8 multi-programmed workloads shows that SLS-CP improves system level speedup and fairness over UCP and IPC-CP.

A stream processor executes an application that has been decomposed into a sequence of kernels that operate on streams of data elements. During the execution of a kernel, all streams accessed must be communicated through the SRF (Stream Register File), a non-bypassing software-managed on-chip memory. Therefore, optimizing utilization of the SRF is crucial for good performance. The key insight is that the interference graphs formed by the streams in stream applications tend to be comparability graphs or decomposable into a set of multiple comparability graphs. We present a compiler algorithm that can find optimal or near-optimal colorings in stream IGs, thereby improving SRF utilization than the First-Fit

BACKGROUND: In the field of RNA secondary structure prediction, the RNAalifold algorithm is one of the most popular methods using free energy minimization. However, general-purpose computers including parallel computers or multi-core computers exhibit parallel efficiency of no more than 50%. Field Programmable Gate-Array (FPGA) chips provide a new approach to accelerate RNAalifold by exploiting fine-grained custom design. RESULTS: RNAalifold shows complicated data dependences, in which the dependence distance is variable, and the dependence direction is also across two dimensions. We propose a systolic array structure including one master Processing Element (PE) and multiple slave PEs for fine grain hardware implementation on FPGA. We exploit data reuse schemes to reduce the need to load energy matrices from external memory. We also propose several methods to reduce energy table parameter size by 80%. CONCLUSION: To our knowledge, our implementation with 16 PEs is the only FPGA accelerator implementing the complete RNAalifold algorithm. The experimental results show a factor of 12.2 speedup over the RNAalifold (ViennaPackage - 1.6.5) software for a group of aligned RNA sequences with 2981-residue running on a Personal Computer (PC) platform with Pentium 4 2.6 GHz CPU.

As the size of large-scale computer systems increases, their mean-time-between-failures are becoming significantly shorter than the execution time of many current scientific applications. To complete the execution of scientific applications, they must tolerate hardware failures. Conventional rollback-recovery protocols redo the computation of the crashed process since the last checkpoint on a single processor. As a result, the recovery time of all protocols is no less than the time between the last checkpoint and the crash. In this paper, we propose a new application-level fault-tolerant approach for parallel applications called the fault-tolerant parallel algorithm (FTPA), which provides fast self-recovery. When fail-stop failures occur and are detected, all surviving processes recompute the workload of failed processes in parallel. FTPA, however, requires the user to be involved in fault tolerance. In order to ease the FTPA implementation, we developed get it fault-tolerant (GiFT), a source-to-source precompiler tool to automate the FTPA implementation. We evaluate the performance of FTPA with parallel matrix multiplication and five kernels of NAS Parallel Benchmarks on a cluster system with 1,024 CPUs. The experimental results show that the performance of FTPA is better than the performance of the traditional checkpointing approach.

The stream architecture is a novel microprocessor architecture with wide application potential. It is critical to study how to use the stream architecture to accelerate scientific computing programs. However, existing stream processors and stream programming languages are not designed for scientific computing. To address this issue, we design and implement a 64-bit stream processor, Fei Teng 64 (FT64), which has a peak performance of 16 Gflops. FT64 supports two kinds of communications, message passing and stream communications, based on which, an interconnection architecture is designed for a FT64-based high-performance computer. This high-performance computer contains multiple modules, with each module containing eight FT64s. We also design a novel stream programming language, stream Fortran 95 (SF95), together with the compiler SF95 compiler, so as to facilitate the development of scientific applications. We test nine typical scientific application kernels on our FT64 platform to evaluate this design. The results demonstrate the effectiveness and efficiency of FT64 and its compiler for scientific computing.

The memory access limits the performance of stream processors. By exploiting the reuse of data held in the Stream Register File (SRF), an on-chip storage, the number of memory accesses can be reduced. In current stream compilers reuse is only attempted for simple stream references, those whose start and end are known. Compiler analysis from outside of stream processors does not directly enable the consideration of other complex stream references. In this paper we propose a transformation to automatically optimize stream programs to exploit the reuse supplied by loop-dependent stream references. The transformation is based on three results: algorithms to recognize the reuse supplied by stream references, a new abstract expression called the Stream Reuse Graph (SRG) to depict the reuse and the optimization of the SRG for the transformation. Both the reuse between whole sequences accessed by stream references and that between partial sequences are exploited in the paper. In particular, the problem of exploiting partial stream reuse does not have its parallel in the traditional data reuse exploitation setting (for scalars and arrays). Finally, we have implemented our techniques using the StreamC/KernelC compiler for Imagine. Experimental results show a resultant speedup of 1.14 to 2.54 times using a range of typical stream processing application kernels.

In high performance parallel computing, energy optimization for parallel loops becomes one key because the time of loops often takes a significant part of the whole execution time. Energy-constrained problem is one of the important research focuses. This paper studies energy-constrained problem based on OpenMP static loop scheduling. Firstly, we propose energy-constrained static scheduling algorithm (ECSS), which utilizes DVS to scale down voltage/frequency of the light-loaded processors in terms of energy constraint. Secondly, we propose Energy Constraint based Performance-Optimal Static Scheduling algorithm (ECPOSS), which combines loop rescheduling and DVS for the better performance under the same energy constraint. We prove ECPOSS can obtain the best performance under the same energy constraint. Through testing NPB3.2-OMP programs on 20-160 multiprocessor simulation environment, we evaluate the effectiveness of our algorithms. Experimental results show the performance of ECPOSS is better than that of ECSS by 4.81% under the 50% energy constraint on 100 processors.

CC-GPFS, a global parallel file system optimized for DSM (distributed shared memory) system is developed. A global cache based on DSM is introduced to reduce file system storage server load and improve clients I/O latency. We focus the design on the global effectiveness of the cache, the speed of remote I/O operations, and simplify the data consistency mechanism for tightly coupled DSM system. Prototype system evaluation results show that CC-GPFS greatly improves I/O throughput by integrating global cache and distributed object-based storage.

Application-level checkpointing is a promising technology in the domain of large-scale scientific computing. The consistency of global checkpoint must be carefully guaranteed in order to correctly restore the computation. Usually, some complex coordinated protocols are employed to ensure the consistency of global checkpoint, which require logging orphan or in-transit messages during checkpointing. These protocols complicate the recovery of the computation and increase the checkpoint overhead due to logging message. In this paper, a new method which ensures the consistency of global checkpoint by static analysis is proposed. The method identifies the safe checkpointing regions in MPI programs, where the global checkpoint is always strongly consistent. All checkpoints are located in those safe checkpoint regions. During checkpointing, the method will not log any messages and introduce no extra overhead. The method was implemented and integrated into ALEC, which is a source-to-source precompiler for automating application-level checkpointing. The experimental results show that our method is effective.

One of the basic problems related to the efficient application-level checkpointing is the placement of checkpoints in the source codes. In this paper we discuss two common questions with a source-to-source precompiler ALEC: 1) if there are N checkpoints in the application's source code, how to pick M checkpoints out of them minimizing the total amount of checkpoint data? 2) if there are no checkpoint in the application's source code, how to insert a set of checkpoints minimizing the amount of checkpoint data? We reveal that these two questions can both be abstracted as a mathematic model which is similar to the 0-1 integer programming model, and the model can be solved using implicit enumeration method. The solving methods proposed in the paper have been implemented and integrated into ALEC. Experimental results show that the method is efficient.

Stream processors, with the stream programming model, have demonstrated significant performance advantages in the domains signal processing, multimedia and graphics applications. In this paper we examine the applicability of a stream processor to 2-D Jacobi iteration which is widely used to solve partial differential equations, an important class of scientific programs. We first map 2-D Jacobi iteration in FORTRAN version to the stream processor in a straightforward way. In a stream processor system, the management of system resources is the programmers' responsibility. We then present several optimizations, which avail the stream program for 2-D Jacobi iteration, called StreamJacobi, of various aspects of the stream processor architecture. Finally, we analyze the performance of StreamJacobi, with different scales, and the presented optimizations. The final stream program StreamJacobi is from 2.31 to 6.42 times faster than the corresponding FORTRAN programs on a Xeon 5100 processor, with the optimizations playing an important role in realizing the performance improvement.

In the field of RNA secondary structure prediction, the Zuker algorithm is one of the most popular methods using free energy minimization. However, general-purpose computers including parallel computers or multi-core computers exhibit parallel efficiency of no more than 50% on Zuker. FPGA chips provide a new approach to accelerate the Zuker algorithm by exploiting fine-grained custom design. Zuker shows complicated data dependences, in which the dependence distance is variable, and the dependence direction is also across two dimensions. We propose a systolic array structure including one master PE and multiple slave PEs for fine grain hardware implementation on FPGA. We exploit data reuse schemes to reduce the need to load energy matrices from external memory. We also propose several methods to reduce energy table parameter size by 85%. To our knowledge, our implementation with 16 PEs is the only FPGA accelerator implementing the complete Zuker algorithm. The experimental results show a factor of 14 speedup over the ViennaRNA-1.6.5 software for 2981-residue RNA sequence running on a PC platform with Pentium 4 2.6 GHz CPU.

Application-level checkpointing can decrease the overhead of fault tolerance by minimizing the amount of checkpoint data. However this technique requires the programmer to manually choose the critical data that should be saved. In this paper, we firstly propose a live-variable analysis method for MPI programs. Then, we provide an optimization method of data saving for application-level checkpointing based on the analysis method. Based on the theoretical foundation, we implement a source-to-source precompiler (ALEC) to automate application-level checkpointing. Finally, we evaluate the performance of five FORTRAN/MPI programs which are transformed and integrated checkpointing features by ALEC on a 512-CPU cluster system. The experimental results show that i) the application-level checkpointing based on live-variable analysis for MPI programs can efficiently reduce the amount of checkpoint data, thereby decrease the overhead of checkpoint and restart; ii) ALEC is capable of automating application-level checkpointing correctly and effectively.

In this paper, we present a detailed case study of the optimizing implementation of a fundamental scientific kernel, matrix-vector multiplication, on FT64, which is the first 64-bit stream processor designed for scientific computing. The major novelties of our study are as follows. First, we develop four stream programs according to different stream organizations, involving dot product, row product, multi-dot product and multi-row product approaches. Second the optimal strip size for partitioning the large matrix is put forward based on a practical parameter model. Finally loop unrolling and software pipelining are used to hide the communications with the computations. The experimental results show that the optimizing implementations on FT64 achieve high speedup over the corresponding Fortran programs running on Itanium 2. It is certain that matrix-vector multiplication can efficiently exploit the tremendous potential of FT64 stream processor through programming optimizations.

Fault tolerance is a critical issue in the arena of large-scale computing. The fault-tolerant parallel algorithm (FTPA) is an application-level technique for tolerating hardware failures. FTPA achieves fast failure recovery making use of parallel recomputing. However, it complicates the coding of the application program. This paper uses compiler technology to automate the design of FTPA, and introduces the implementation of a tool called GiFT (Get it Fault-Tolerant). GiFT utilizes the extended data-flow analysis to choose the state needed by failure recovery, exploits the parallel recomputing time model to compute the optimal number of recomputing processes, and uses parallelization technologies to generate parallel recomputing codes. The experimental results show that original MPI programs can be transformed into the FTPA counterparts by GiFT correctly, and the performance of GiFT-generated FTPA programs is comparable to the performance of hand-modified FTPA programs.

In HPC, power-related concern becomes dominant aspects of hardware and software design. Significant research effort has been devoted towards the energy optimization of parallel loop. This article is focused on energy-oriented OpenMP static and dynamic parallel loop scheduling problem. Only DVS cannot obtain the maximum energy savings. It is necessary to combine parallel loop rescheduling and DVS. First, we propose an energy-saving static scheduling (ESSS) algorithm, which exploits the scheduling slack to save energy by DVS. Second, we propose an energy-saving optimal static scheduling (EOSS) algorithm, which obtains the maximum energy saving through combining loop rescheduling and DVS. Last, in order to reduce the energy of OpenMP dynamic scheduling, we shut down the processor when it is idle, which is called shut-down based dynamic scheduling (SBDS) algorithm. Finally, we demonstrate the effectiveness by experiments.

Stream processors, developed for the stream programming model, perform well on media applications. In this paper we examine the applicability of a stream processor to scientific computing applications. Eight scientific applications, each having different performance characteristics, are mapped to a stream processor. Due to the novelty of the stream programming model, we show how to map programs in a traditional language, such as FORTRAN. In a stream processor system, the management of system resources is the programmers' responsibility. We present several optimizations, which enable mapped programs to exploit various aspects of the stream processor architecture. Finally, we analyze the performance of the stream processor and the presented optimizations on a set of scientific computing applications. The stream programs are from 1.67 to 32.5 times faster than the corresponding FORTRAN programs on an Itanium 2 processor, with the optimizations playing an important role in realizing the performance improvement.

This paper describes a graph coloring compiler framework to allocate on-chip SRF(Stream Register File) storage for optimizing scientific applications on stream processors. Our framework consists of first applying enabling optimizations such as loop unrolling to expose stream reuse and opportunities for maximizing parallelism, i.e., overlapping kernel execution and memory transfers.Then the three SRF management tasks are solved in a unified manner via graph coloring: (1) placing streams in the SRF, (2) exploiting stream use, and (3) maximizing parallelism. We evaluate the performance of our compiler framework by actually running nine representative scientific computing kernels on our FT64 stream processor. Our preliminary results show that compiler management achieves an average speedup of 2.3x compared to First-Fit allocation. In comparison with the performance results obtained from running these benchmarks on Itanium 2, an average speedup of 2.1x is observed.

This paper proposes an optimization method of data saving for application-level checkpointing based on the live-variable analysis method for MPI programs. We presents the implementation of a source-to-source precompiler (CAC) for automating applicationlevel checkpointing based on the optimization method. The experiment shows that CAC is capable of automating application-level checkpointing correctly and reducing checkpoint data effectively.

The efficiency of scientific applications on the Imagine stream processor is increasingly concerned by researchers. One of the obstacles is that the programming language of Imagine does not target the scientific computing. This paper introduces a program transformation algorithm to automatically transform loops to the stream programs executed on Imagine. The optimization for memory accessing is also considered during the transformation. We have implemented the transformation and optimization algorithm with the GFORTRAN frontend. Preliminary results over benchmark kernels show that our approach is a convenient and efficient solution to develop scientific applications on the Imagine stream processor.

The fast and accurate evaluation of transcendental functions (e.g. exp, log, sin, and atan) is quite important in many domains. We implement a software inline function library that can be called from KernelC programming language to compute 8 typical functions on Imagine architecture. By exploiting some of the key features of Imagine architecture, we have been able to provide single precision transcendental functions that are very accurate yet can typically be evaluated to get 16 function values in between 18 and 43 clock cycles. In this paper, we also discuss the algorithms and implementation details of these functions.

Stream architecture is a novel microprocessor architecture with wide application potential. But as for whether it can be used efficiently in scientific computing, many issues await further study. This paper first gives the design and implementation of a 64-bit stream processor, FT64 (Fei Teng 64), for scientific computing. The carrying out of 64-bit extension design and scientific computing oriented optimization are described in such aspects as instruction set architecture, stream controller, micro controller, ALU cluster, memory hierarchy and interconnection interface here. Second, two kinds of communications as message passing and stream communications are put forward. An interconnection based on the communications is designed for FT64-based high performance computers. Third, a novel stream programming language, SF95 (Stream FORTRAN95), and its compiler, SF95Compiler (Stream FORTRAN95 Compiler), are developed to facilitate the development of scientific applications. Finally, nine typical scientific application kernels are tested and the results show the efficiency of stream architecture for scientific computing.

Without reliable trust relationship established between cooperative parties, the paradigm of large-scale resource sharing and cooperative problem solving as envisioned by most will not come true in grid. What's more, for the scale and openness of grid environment, cooperation often occurs among completely unknown entities, where traditional identity-based trust system obviously cannot work well for its restricted scalability and flexibility. In this paper, we propose a pre-evaluating set based trust model, which resorts to reputation mechanisms for trust establishment. The introduction of the pre-evaluating set is to track an entity's rating criteria, overcome the prevalent strangeness of grid entities. With this pre-evaluating set, we can reasonably filter out malicious ratings by examining inconsistency between ratings to this set and to real transactions, effectively tune a rater's bias to cater to the current evaluator's criteria by interpolation approach and scientifically weight a rater's rating in aggregation by the introduction of criteria coherent degree which describes the similarity between an entity's rating criteria and the current evaluator's.

Reputation-based trust system emerges as a promising mechanism for trust establishment between unknown entities in grid, in which the reliability of first-hand ratings plays a crucial part. In this paper, we propose a pre-evaluating set based bias-tuned approach for dishonest feedback filtering in such system, which has taken reputation's subjective feature into consideration. With the fact that different rater may have different rating criteria in mind, our filtering method will not blindly filter out apparently dishonest feedbacks such as higher ratings from lenient raters. The basic idea for filtering is that, first align ratings according to some same rating criteria and then try to find inconsistency among tuned ratings. Specifically, rating criteria is tracked by means of the pre-evaluating set introduced especially to our trust model. Tuning is performed according to the current evaluator's rating criteria with an interpolation method. Inconsistency examination consists of two aspects "credibility filtering" and "on-spot filtering". The former tries to find inconsistency in ratings given to entities familiar to the current evaluator. And the latter tries to find inconsistency in the currently retrieved ratings. With a two-dimension function, results from these two filtering are combined. Experiment results show that we can effectively filter out dishonest feedbacks and retain honest ones both to a large extent

The paper presents a novel framework for scalable model checking of concurrent C programs. With the idea of verification reuse, it shows an integrated approach to efficient reduction of state space by abstraction, symbolic representation and dynamic partial-order reduction (DPOR) techniques. The framework is founded on an over-approximated model of the concurrent program by variable abstraction, and combines DPOR with lightweight symbolic execution to generate the symbolic conditions for all locations, called -conditions, which are intended for verification reuse. The -conditions of a location are weak approximation of the conditions that must be satisfied at that location so as to guarantee the temporal safety properties to be verified. These conditions will be checked for reusing the previous exploration in verification, and will be iteratively refined under the guidance of spurious counterexamples. The presented framework is demonstrated by several experiments including a concurrent software system whose server and client processes are derived from openssl-0.9.6c C source codes implementing the SSL protocol.

Reputation-based trust system emerges as a promising mechanism for trust establishment between unknown entities in Grid, in which the reliability of first-hand ratings plays a crucial part. In this paper, we propose a pre-evaluating set based bias-tuned approach for dishonest feedback filtering in such system, which has taken reputation's subjective feature and Grid entity's prevailing strangeness into consideration. The basic idea for filtering is to find inconsistency between a rater's ratings and his usual rating habit. The introduction of the pre-evaluating set is to provide a way for rating habit tracking. The proposed filtering method consists of two parts: "credibility filtering" and "on-spot filtering". The former tries to find inconsistency in ratings given to entities familiar to the current evaluator. And the latter tries to find inconsistency in the current retrieved rating. In combination of the two parts, we can effectively filter out dishonest feedbacks and retain honest ones to a large extent.

Abstract ChinaGrid is an important project sponsored by the China Ministry of Education, aiming to provide high‐performance services in a Grid computing environment. In this paper, one of the applications offered by ChinaGrid, parallel remote‐sensing image processing, is described. Geometric correction is a basic step during the processing of remote‐sensing imagery, which is traditionally a computation‐intensive and communication‐intensive application if in parallel mode. In order to move this application into a Grid, a new Grid‐enabled parallel algorithm of geometric correction is proposed, called GPGC. GPGC changes the frequent and fine‐grain communication mode of the existing parallel method into a delayed but concentrated exchanging mode by computing an irregular local output area. This change means no communication or synchronization happens during resampling that occupies most of the execution time. To prove its efficiency, the complexity of GPGC is analyzed in theory. Finally, performance testing of GPGC and its application in ChinaGrid are given. Experimental results show that our algorithm is more suitable for a Grid platform, excelling the old method in both performance and salability. Copyright © 2006 John Wiley & Sons, Ltd.

This paper presents a novel method, namely slicing execution, for model checking C programs with respect to temporal safety properties. The distinguished feature is that it shows a nice approach to the efficient reduction of state space by abstraction and symbolic representation. Slicing execution is founded on an over-approximated semantics of C programs by variable abstraction, and executes symbolically only the relevant statements under abstraction criteria to construct over-approximated finite models of programs, which may be model checked. The variable abstraction criterion begins with a proper initial set of program variables and may be iteratively refined according to spurious counterexamples generated during model checking. In general, the properties to be verified often involve only a few variables in practical programs. In these cases, significant state space reduction, as well as considerable improvement of the scalability, may be achieved. The presented method has been used to verify the initial handshake process of SSL protocol based on the C source code of openssl-0.9.6c. The experiment results confirm that slicing execution is not only practical but also effective.

With the increasing importance of multiple multiplatform remote sensing missions, fast and automatic integration of digital data from disparate sources has become critical to the success of these endeavors. Firstly, an overview of development of automatic and parallel global image registration is given. And then, based on the analyses of existing three parallel methods of wavelet-based global registration, a new parallel strategy is proposed. Moreover, towards the quantitative evaluation, first results of the intercomparision of four parallel global registration algorithms are presented in theory and in experiments.

As energy consumption becoming one of the key optimization objects in on-chip multiprocessor, compiling a parallelizing application combined with energy saving strategy is more significant. In this paper, we focus on an on-chip multiprocessors architecture, where each processor in on-chip multiprocessor can independently adjust its frequency and voltage for energy savings. Given an arrayintensive application, we simulate parallelizing application and analyze probable load imbalance; then our energy saving strategy determines each processor’s clock frequency and voltage level fit for each parallel fragment in terms of load imbalance. Here, parallel fragments mainly denote parallel loop nests. Further, we consider the serial code fragments as a severe load-unbalanced parallel partitioning when the redundant processors can be shut down. Initial experiment proves our energy saving strategy is successful in reducing the energy consumption of the parallel programs.

With service-oriented architecture entering into the mainstream and the fundamental role security service played in Grid computing, it is necessary and commonplace to integrate security service(s) with other Grid services. However, current ad-hoc, handcrafted and proprietary integrating manners greatly hinder the the newly-integrated service’s QoS (Quality of Service) and QoP (Quality of Protection). Efficient and effective security-service integration entails a higher-level abstraction of specific integration scenarios. That’s where this paper takes root. In this paper, we borrow some idea from software engineering and propose several integration patterns of Grid security service. According to the number of the to-be-integrated non-security service(s), we classify all the patterns into 2 kinds: bilateral patterns and multilateral patterns, and propose 6 patterns (binding, on-demand, tailor, composite, contract and migration) and 4 patterns (separated, shared, mediated and enhanced) respectively. For each pattern, we discuss its intent, applicability, participants and consequences.