Cluster and grid computing is a relatively new interdisciplinary field, where computer science, engineering and computational biology as its core supporting disciplines. The rise of cluster and grid computing discipli...
详细信息
The parentheses matching problem is to determine the mate of each parenthesis in a balanced string of n parentheses. In this paper, we present three novel and elegant parallel algorithms for this problem on parallel r...
详细信息
The grid enables large-scale resource sharing and makes it viable for running large-scale parallel and distributed simulations. The high level architecture (HLA) paradigm provides a software platform and interoperabil...
详细信息
ISBN:
(纸本)9780769520360
The grid enables large-scale resource sharing and makes it viable for running large-scale parallel and distributed simulations. The high level architecture (HLA) paradigm provides a software platform and interoperability interface for simulation components to utilize these hardware resources. However, neither the grid nor the HLA provides mechanism for resource management for parallel and distributed simulations. It is also noticed that substantial effort is required for writing program that conforms to the runtime infrastructure (RTI) requirements because of its complexity. In this paper, we introduce a framework for designing and executing parallel simulation using the RTI. The framework is also designed to assist load balancing and checkpointing. With the code library from our framework, the modeler is able to complete the design of a parallel simulation that runs on RTI by specifying the simulation configuration and the handling detail of each event. Our framework incorporates automatic code generation. It also uses data distribution management (DDM) to route simulation events (interactions) to achieve efficient use of network bandwidth.
In this paper an Algorithm Based Error Detection (ABED) scheme is applied to the multigrid algorithm which provides an iterative solution to a system of linear algebraic equations resulting from a finite difference di...
详细信息
In this paper an Algorithm Based Error Detection (ABED) scheme is applied to the multigrid algorithm which provides an iterative solution to a system of linear algebraic equations resulting from a finite difference discretization of a Poisson equation. Invariants are created to implement checking in the relaxation, restriction and interpolation operators. Modifications to invariants due to roundoff errors accumulated within the operators which often lead to a situation known as false alarms have been addressed by deriving the expressions for the roundoff errors in the algebraic processes in the operators and correcting the invariants accordingly. ABED encoded multigrid algorithm is shown to be insensitive to the size and the range of the input data, besides providing excellent error coverage at a low latency for floating point integer and memory errors.
For heterogeneous dynamic short-range molecular dynamics simulations it is critical to employ suitable load-balancing methods to minimize the time to solution. However, designing and parametrizing the optimal load-bal...
详细信息
ISBN:
(纸本)9781509057740
For heterogeneous dynamic short-range molecular dynamics simulations it is critical to employ suitable load-balancing methods to minimize the time to solution. However, designing and parametrizing the optimal load-balancing method is a complex task, depending on detailed properties of the simulation *** main challenge in balancing the load of molecular dynamics simulations is the extreme difference in load density for scenarios with heterogeneous particle density, which can easily reach 4-6 orders of magnitude. Therefore, heterogeneity is deemed to be a relevant property and a suitable metric to reliably quantifying heterogeneity is formulated. This metric, which is based on binning particles and evaluating statistical moments, is then applied to example scenarios and correlated to the performance of five load balancing methodologies. Furthermore, how rapidly the load varies over time will determine how long the benefits of a specific partitioning are expected to last. We deem this to be another relevant property, the dynamics, and introduce corresponding metrics. The results indicate that these metric are useful to differentiate between scenarios and facilitate reasoning over the complex relationship between particle simulation scenarios and optimal load balancing methods. This work is a first step towards understanding this relationship, while introducing key concepts we regard as a crucial for this understanding.
The approaches to deal with scheduling and load balancing on PC-based cluster systems are famous and well-known. Self-scheduling schemes, which are suitable for parallel loops with independent iterations on cluster co...
详细信息
Algebraic factorization is an extremely important part of any logic synthesis system, but it is computationally expensive. Hence, it is important to look at parallel processing to speed up the procedure. This paper pr...
详细信息
Algebraic factorization is an extremely important part of any logic synthesis system, but it is computationally expensive. Hence, it is important to look at parallel processing to speed up the procedure. This paper presents three different parallel algorithms for algebraic factorization. The first algorithm uses circuit replication and uses a divide-and-conquer strategy. A second algorithm uses totally independent factorization on different circuit partitions with no interactions among the partitions. A third algorithm represents a compromise between the two approaches. It uses a novel L-shaped partitioning strategy which provides some interaction among the rectangles obtained in various partitions. For a large circuit like ex1010, the last algorithm runs 11.5 times faster over the sequential kernel extraction algorithms of the SIS sequential circuit synthesis system on six processors with less than 0.2% degradation in quality of the results.
Algebraic factorization is an extremely important part of any logic synthesis system but it is computationally expensive. Hence it is important to speed it up. The paper presents an algorithm to speedup the factorizat...
详细信息
Algebraic factorization is an extremely important part of any logic synthesis system but it is computationally expensive. Hence it is important to speed it up. The paper presents an algorithm to speedup the factorization by partitioning the circuit and performing factorizations on the sub-circuits. The approach clusters the entries of the co-kernel cube matrix into dense blocks using a novel L-shaped partitioning and searches these blocks for kernels. The L-shaped approach runs up to five times faster than the kernel extraction routine in SIS.
Simulated annealing based standard cell placement for VLSI designs has long been acknowledged as a compute-intensive process. All previous work in parallel simulated annealing based placement has minimized area, but w...
详细信息
Simulated annealing based standard cell placement for VLSI designs has long been acknowledged as a compute-intensive process. All previous work in parallel simulated annealing based placement has minimized area, but with deep submicron design, minimizing wirelength delay is also needed. The algorithm discussed in this paper is the first parallel algorithm for timing driven placement. We have used a very accurate Elmore delay model which is more complete intensive and hence the need for parallel placement is more apparent. parallel placement is also needed for very large circuits that may not fit in the memory of a single processor. Therefore, our algorithm is circuit partitioned and can handle arbitrary large circuits on distributed memory multiprocessors. The algorithm, called mpi PLACE, has been tested on several large benchmarks on a variety of parallel architectures.
暂无评论