Modern memory management systems suffer from poor performance and subtle concurrency bugs, slowing down applications while introducing security vulnerabilities. We observe that both issues stem from the conventional design of memory management systems with two levels of abstraction: a software-level abstraction (e.g., VMA trees in Linux) and a hardware-level abstraction (typically, page tables). This design increases portability but requires correctly and efficiently synchronizing two drastically different and complex data structures, which is generally challenging.

The Single-Source Shortest Path (SSSP) problem is to compute the shortest distances in a weighted graph from a source vertex to every other vertex. This paper focuses on parallel efficiency and scalability of SSSP computations on large-scale graphs. We propose an edge-fencing strategy to customize a SSSP algorithm's schedule for every SSSP computation, and devise a path-centric SSSP algorithm with this strategy. This strategy aims at reducing both the relaxed edges and relaxations repeated on each edge. It exploits a few fence values to select the relaxed edges and schedule edge relaxations according to lengths of the created paths. The path-centric algorithm works on a hierarchical graph model, and exploits the edge-fencing strategy to schedule edge relaxations in parallel settings. The hierarchical graph model quantifies the length distribution of shortest paths in large-scale graphs, provides appropriate fence values for every SSSP computation. The algorithm was evaluated on a wide range of synthetic graphs and real-world graphs. The experimental results suggest that our algorithm is efficient and scalable for graphs with skewed degree distributions, and its performance is relatively insensitive to the hierarchical graph model's accuracy.

Breadth-first search (BFS) is a widely used graph algorithm. It is data-intensive, and the data accesses are random and discontinuous. The data-accessing latency plays an important role in the algorithm's time consumption on shared memory computers, since it can hardly be reduced with processor technologies like dynamic execution of instructions and prefect of data. This work focuses on partitioning computation for BFS on shared memory computers. The goal is to improve data-accessing efficiency and optimize load balance among processors. A data-centric parallel computing model is presented. The model provides a partitioned and hierarchical data-view for each processor, and automatically assigns the computation on each data partition to a set of processors that have same data-view. This computation partitioning mechanism allows applications to minimize data accessing collisions among processors. A BFS equipped with the data-centric computation partitioning mechanism has been implemented. Two strategies are introduced to improve our BFS's performance further. One is to improve vertex -- accessing efficiency by representing status of vertices with bitmap. Another is to improve load balance by adjusting every processor's workload dynamically. The model and the strategies have been evaluated with both real graphs and synthetic graphs. Comparing with the BFS without the data-centric computation partitioning mechanism, the new BFS has achieved 1.8-2.6× speedup. We believe this mechanism is also applicable to other graph applications.

UNLABELLED: We have developed a package named Application for Bioinformatics Computing Grid (ABCGrid). ABCGrid was designed for biology laboratories to use heterogeneous computing resources and access bioinformatics applications from one master node. ABCGrid is very easy to install and maintain at the premise of robustness and high performance. We implement a mechanism to install and update all applications and databases in worker nodes automatically to reduce the workload of manual maintenance. We use a backup task method and self-adaptive job dispatch approach to improve performance. Currently, ABCGrid integrates NCBI_BLAST, Hmmpfam and CE, running on a number of computing platforms including UNIX/Linux, Windows and Mac OS X. AVAILABILITY: The source code, executables and documents can be downloaded from http://abcgrid.cbi.pku.edu.cn

Bioinformatics grid has emerged to meet the sharp requirement for computation and storage resource in the bioinformatics research field. In this paper, a design of SOA-based bioinformatics grid system is put forward under the WSRF specification. It aggregates existing tools such as BLAST, wrapped as Web services, through WS-ServiceGroup, and supports the development, deployment, execution and monitoring of complex bioinformatics grid application. Based on the supporting environment, applications can access bioinformatics resource in a transparent manner. This paper also presents a use case to show the process of workflow building, execution and monitoring

Many modern scientific applications consist of numerous executions of legacy programs. The repetitive but discontinuous resource access pattern in these applications causes challenge in solving them with grid technologies. A stateful Web service model is proposed, which exploits the factory/instance pattern to schedule resources according to job submitters instead of submitted jobs. Each instance represents a customized execution environment that is exclusively accessed by one job submitter, and can be accessed repetitively to perform as many jobs as desired. At the same time, this model introduces an individualizing operation for every instance, which provides a mechanism to minimize the amount cost of remote data accesses required by all jobs submitted to the instance. This service model is exploited in enabling and optimizing repetitive resource accesses that occur in AS applications