As new genes are sequenced, it is common for molecular biologists to compare the new gene's DNA to known sequences. One simple form of DNA sequence comparison is done by solving the Longest Common Subsequence (LCS...
详细信息
ISBN:
(纸本)9780889866386
As new genes are sequenced, it is common for molecular biologists to compare the new gene's DNA to known sequences. One simple form of DNA sequence comparison is done by solving the Longest Common Subsequence (LCS) problem. In this paper, we propose a parallel algorithm and specialized FPGA-based processor (the associative ASC Processor with reconfigurable 2D mesh) to solve the exact and approximate match LCS problems. This solution uses inexpensive hardware and can be reconfigured as new analysis techniques are developed, making it particularly attractive for processing biosequences.
A stabilizing system guarantees that, regardless of the current configuration, the system reaches a legal configuration in a bounded number of steps and the system configuration remains legal thereafter. Whereas, a st...
详细信息
ISBN:
(纸本)9780889867741
A stabilizing system guarantees that, regardless of the current configuration, the system reaches a legal configuration in a bounded number of steps and the system configuration remains legal thereafter. Whereas, a stabilizing system that maintains no explicit variables in the processes of the system is referred to as an inherently stabilizing system, and hence all system states are legal by construction. Due to this attribute, inherently stabilizing systems are immune to transient faults and do not experience any delay due arbitrary system initialization. We view a fault that perturbs the system configuration but not the program as transient fault. Due to these features, inherently stabilizing distributed protocols for peer-to-peer, sensor and mobile networks are desirable. Hypercube, star networks and their variations that provide an increased degree of scalability have been initially design for parallel networks. However, their scalability and the presence of multiple disjoint paths in these topologies make them viable alternatives to existing peer-to-peer and sensor networks topologies. In this paper, we proposed an inherently stabilizing algorithm for delivering messages over all node-disjoint paths from a process to another in star networks. The proposed algorithm has numerous applications including VLSI layout, reliable networks routing, secure message transmission, and network survivability. The proposed routing algorithm is optimal with respect to its state space and lengths of the node-disjoint paths.
Molecular dynamics simulations are widely used for sim- ulating the motion of molecules in order to gain a deeper understanding of chemical reactions, fluid flow, phase tran- sitions, and other physical phenomena due ...
详细信息
ISBN:
(纸本)9780889868786
Molecular dynamics simulations are widely used for sim- ulating the motion of molecules in order to gain a deeper understanding of chemical reactions, fluid flow, phase tran- sitions, and other physical phenomena due to molecular in- teractions. However, these simulations require huge com- puter resources. In addition, the problem of energy con- sumption must be solved. Recently, GPGPU has attracted attention as a possible solution to these problems. In this paper, we performed molecular dynamics simulations on a CPU and GPU, and compare calculation time, power con- sumption and energy consumption results between them.
Splitting and executing different parts of a system with the help of a set of dedicated servers is the most widely used technique for making it scalable. However, it introduces synchronisation issues and requires spec...
详细信息
ISBN:
(纸本)9780889868786
Splitting and executing different parts of a system with the help of a set of dedicated servers is the most widely used technique for making it scalable. However, it introduces synchronisation issues and requires special attention. Synchronisation is extensively investigated for parallel and distributedsystems and generally centralised or distributed approaches are used to obtain a consistent view of a system. Centralised methods are easy to implement and achieve precise synchronisation but are not scalable. On the other hand, distributed methods are difficult to manage and introduce potential communication overhead. They also introduce longer delays due to dependencies among components at different levels when used with conservative strategies and complex hierarchical models. In this paper, we propose a fully decentralised synchronisation mechanism to maintain a consistent view of a virtual world. It greatly reduces communication overhead by restricting a server simulating a region to synchronise itself with the servers executing regions sharing boundaries (we define them as adjacent regions) with it. It maintains traditional synchronisation constraints. The proposed mechanism is illustrated with the help of simple scenarios and an abstract model is used to compare it with traditional approaches. It is demonstrated that number of intermediate points among servers and thus complexity and delay in traditional approaches increase significantly with an increase in number of levels in a hierarchy.
Operating system virtualization has recently become a popular technique to achieve better resource utilization in so-called '' server farm '' environments. This technique provides a virtual hardware in...
详细信息
ISBN:
(纸本)9780889866379
Operating system virtualization has recently become a popular technique to achieve better resource utilization in so-called '' server farm '' environments. This technique provides a virtual hardware interface on top of which one can run multiple instances of popular operating systems. The Xen Virtual Machine Monitor is an implementation of operating system virtualization that supports live migration, the transfer of a virtual operating system from one physical machine to another with minimal down time. We have utilized this capability to implement a monitoring and dynamic reconfiguration daemon that attempts to equalize the load on all host nodes in a group of machines running Xen. We have also implemented a simulator for testing balancing algorithms. Experiments using these tools have provided insight into the redistribution of virtualized operating systems and how this differs from the more thoroughly-studied problem of process-level load balancing.
This work presents a parallel implementation of the implicitly restarted Arnoldi/Lanczos method for the solution of eigenproblems approximated by the finite element method. The implicitly restarted Arnoldi/Lanczos use...
详细信息
ISBN:
(纸本)9780889868113
This work presents a parallel implementation of the implicitly restarted Arnoldi/Lanczos method for the solution of eigenproblems approximated by the finite element method. The implicitly restarted Arnoldi/Lanczos uses a restart scheme in order to improve the convergence of the desired portion of the spectrum, maintaining the orthogonality of the Krylov basis. The presented implementation is suitable for distributed memory architectures, specially PC clusters. In the parallel solution, a subdomain by subdomain approach was implemented and overlapping and non-overlapping mesh partitions were used. Compressed data structures in the formats CSRC and CSRC/CSR were used to store the global matrices coefficients. The parallelization of numerical linear algebra operations presented in both Krylov and implicitly restarted methods are discussed. In order to point out the efficiency and applicability of the proposed algorithms, a numerical example is shown.
Currently, the computational needs of scientific applications have grown to levels where it is necessary to have computers with a very high degree of parallelism. The IBM Blue Gene/L can hold in excess of 200K process...
详细信息
ISBN:
(纸本)9780889867741
Currently, the computational needs of scientific applications have grown to levels where it is necessary to have computers with a very high degree of parallelism. The IBM Blue Gene/L can hold in excess of 200K processors and it has been designed for high performance. However, failures in this large system are a major concern, since it has been demonstrated that a failure will drastically decrease the performance of the system. Checkpointing and log schemes have been utilized to overcome these failures, however, it has been shown that these techniques are not as effective as desired. Therefore, proactive failure detection and prediction has gained interest in the research community. In this study, we have collected the RAS event and Job logs from a large IBM Blue Gene/L over a three-month period. We have investigated the relationship among fatal and non-fatal events with the aim of proactive failure prediction. Based on our observations, we have developed a scheme for predicting fatal events based on the spatial and temporal relation among fatal and nonfatal events. We will show that with our scheme up to 84% of fatal events could be effectively predicted.
With increased globalization, most databases are now highly distributed. Thus, there is a need to reduce the cost of queries that require data from several locations. In the literature, the semijoin is the most common...
详细信息
ISBN:
(纸本)9780889868786
With increased globalization, most databases are now highly distributed. Thus, there is a need to reduce the cost of queries that require data from several locations. In the literature, the semijoin is the most commonly used operation for the reduction phase of any distributed query optimization strategy. In [7] an improvement, called the 2-way semijoin, is proposed. The authors conclude that the 2-way semijoin has greater reduction power than the traditional semijoin and has a greater propagation of reduction effects on other relations. However, they were comparing their 2-way semijoin to a single semijoin. In this paper, we decided to compare the 2-way semijoin with 2 separate semijoins. This seems to be a better comparison. We designed an algorithm and performed some experiments to investigate the claims made about the 2-way semijoin. We conclude that the 2-way semijoin is better than two separate semijoins under certain conditions. We also comment on the propagation effects of reductions made by using two separate semijoins.
Passive testing is a technique suitable for continuous, non-intrusive, autonomous testing of qualitative behavioural properties (correctness) of a deployed distributed system. A real passive tester has to face observa...
详细信息
ISBN:
(纸本)9780889866379
Passive testing is a technique suitable for continuous, non-intrusive, autonomous testing of qualitative behavioural properties (correctness) of a deployed distributed system. A real passive tester has to face observational uncertainty, which may lead to false verdicts. We submit the novel idea of a self-tuned passive tester, which is able to adapt to a priori unknown, and possibly changing delays in communication channels. We propose the structure and algorithms of a passive tester that "tunes itself" basing solely on its own, locally issued verdicts. This seemingly counter-intuitive principle is shown by simulation to be viable and effective.
Dynamic server resource allocation to services on networks, or utility computing, is a powerful technology to provide required computer resources for multiple service providers at low cost. Virtual machine (VM) techno...
详细信息
ISBN:
(纸本)9780889866386
Dynamic server resource allocation to services on networks, or utility computing, is a powerful technology to provide required computer resources for multiple service providers at low cost. Virtual machine (VM) technology can be combined with utility computing to further improve server resource utilization. An important technical issue about VM-based utility computing is optimal placement of VMs on physical server nodes, because performance of services may be seriously affected by VM placement. We address this issue by introducing an on-line placement algorithm on the basis of performance influence among services. We have implemented this algorithm and evaluated on a simulated environment. The results have shown that the proposed mechanism can get roughly 25% better score calculated by the placement rules compared with a random placement algorithm.
暂无评论