Network based distributed computing has been gaining popularity over the past decade. Many parallel programming languages and related parallel programming modes are becoming widely accepted. However, the execution of ...
详细信息
Network based distributed computing has been gaining popularity over the past decade. Many parallel programming languages and related parallel programming modes are becoming widely accepted. However, the execution of parallel applications on distributed systems has been hampered by the high communication overhead. To reduce the communication overhead and the completion time of a parallel application, we propose a key message model for parallel computing on network of workstations (NOWs). In the key message model, all messages generated in a key message path are prioritized. A key message path in a task graph is defined as the path that is optimized by the key message algorithm. All messages generated in a key message path are prioritized. Besides, the key message algorithm automatically finds the key message paths. In this paper, we first describe the algorithm that identifies the key messages to be prioritized in a parallel application, then analyze the cost of the algorithm, and finally evaluate the performance of the algorithm in a simulation. Our preliminary analysis of the algorithm shows improvement over the system which does not use prioritization scheme.
Introduces algorithms which can produce both optimal and suboptimal task assignments to minimize the probability of failure of an application executing on a heterogeneous distributed computing system. A cost function ...
详细信息
Introduces algorithms which can produce both optimal and suboptimal task assignments to minimize the probability of failure of an application executing on a heterogeneous distributed computing system. A cost function which defines this probability under a given task assignment is derived. To find optimal and suboptimal task assignments efficiently, a reliable matching and scheduling problem is converted into a state-space search problem in which the cost function derived is used to guide the search. The A* algorithm for finding optimal task assignments and the A*/sub m/ and hill-climbing algorithms for finding suboptimal task assignments are presented. simulation results are provided to confirm the performance of the proposed algorithms.
Data distribution management (DDM) is one of the services defined by the DoD High Level Architecture. DDM is necessary to provide efficient, scalable mechanisms for distributing state updates and interaction informati...
详细信息
Data distribution management (DDM) is one of the services defined by the DoD High Level Architecture. DDM is necessary to provide efficient, scalable mechanisms for distributing state updates and interaction information in large scale distributedsimulations. We describe data distribution management mechanisms (also known as filtering) used for real time training simulations. We propose a new DDM approach to multicast group allocation, which we refer to as a dynamic grid-based allocation. Our scheme is based on a combination of a fixed grid-based method, known for its low overhead and ease of implementation, and a sender-based strategy, which uses fewer multicast groups than the fixed grid-based method. We describe our DDM algorithm, its implementation, and report on the performance results that we have obtained using the RTI-Kit framework. These results include the outcome of experiments comparing our approach to the fixed grid-based method, and they show that our scheme is scalable and significantly reduces the message overhead of previous grid-based allocation schemes.
Multi-agent systems comprise multiple, deliberative agents embedded in and recreating patterns of interactions. Each agent's execution consumes considerable storage and calculation capacities. For testing multi-ag...
ISBN:
(纸本)9780769506678
Multi-agent systems comprise multiple, deliberative agents embedded in and recreating patterns of interactions. Each agent's execution consumes considerable storage and calculation capacities. For testing multi-agent systems, distributedparallelsimulation techniques are required that take the dynamic pattern of composition and interaction of multi-agent systems into account. Analyzing the behavior of agents in virtual, dynamic environments necessitates relating the simulation time to the actual execution time of agents. Since the execution time of deliberative components can hardly be foretold, conservative techniques based on lookahead are not applicable. On the other hand, optimistic techniques become very expensive if mobile agents and the creation and deletion of model components are affected by a rollback. The developed simulation layer of JAMES (a Java Based Agent Modeling Environment for simulation) implements a moderately optimistic strategy which splits simulation and external deliberation into different threads and allows simulation and deliberation to proceed concurrently by utilizing simulation events as synchronization points.
Algorithms for simulating an ATM switch on a distributed memory multiprocessor are described. These include parallel generation of bursty arrival streams, along with the marking and deleting of lost cells due to buffe...
ISBN:
(纸本)9780769506678
Algorithms for simulating an ATM switch on a distributed memory multiprocessor are described. These include parallel generation of bursty arrival streams, along with the marking and deleting of lost cells due to buffer overflows. These algorithms increase the amount of computation carried out independently by each processor, and reduce the communication between the processors. When the number of cells lost is relatively small, the run time of the simulation is approximately O(N/P), where N is the total number of cells simulated and P is the number of processors. The cells are processed in intervals of fixed length; that length affects the structure and the performance of the algorithms.
The concept of strong groups is introduced to describe the structure of simulation models. It is shown that logical processes within strong groups process at approximately the same rate and that different strong group...
详细信息
ISBN:
(纸本)9780769506678
The concept of strong groups is introduced to describe the structure of simulation models. It is shown that logical processes within strong groups process at approximately the same rate and that different strong groups can progress at different rates. An algorithm based on the rates of the strong groups is presented to balance the load among the physical processors and for flow control.
The simulation of wide area computer networks is one area where the benefits of parallelsimulation have been clearly demonstrated. Here we present a description of a system that uses a parallel discrete event simulat...
详细信息
ISBN:
(纸本)9780769506678
The simulation of wide area computer networks is one area where the benefits of parallelsimulation have been clearly demonstrated. Here we present a description of a system that uses a parallel discrete event simulator to act as a high speed network emulator. With this, real Internet Protocol (IP) traffic generated by application programs running on user workstations can interact with modelled traffic in the emulator, thus providing a controlled test environment for distributed *** network emulator uses the TasKit conservative parallel discrete event simulation (PDES) kernel. TasKit has been shown to be able to achieve improved parallel performance over existing conservative and optimistic PDES kernels, as well as improved sequential performance over an existing central-event-list based kernel. This paper explains the modifications that have been made to TasKit to enable real-time operation along with the emulator interface that allows the IP network simulation running in the TasKit kernel to interact with real IP clients. Initial emulator performance data is included.
Scalability is recognised as a primary factor to be considered in the design of distributed systems. The scalability of object-oriented middleware CORBA is becoming a major concern as it has emerged as a standard arch...
详细信息
Scalability is recognised as a primary factor to be considered in the design of distributed systems. The scalability of object-oriented middleware CORBA is becoming a major concern as it has emerged as a standard architecture for distributed object computing. In this paper, a systematic scalability analysis of the basic components of the CORBA specification is attempted. From this analysis, the Portable Object Adapter (POA) and the Implementation Repository (IR) are identified to influence the scale of a CORBA-based system. The specification of the POA provides enough feasibility for the application designer to handle scalability. The existing implementations of IR have a tradeoff between scalability and object migration. A scalable design of the IR is proposed which allows individual objects to migrate without compromising scalability. A performance comparison of the proposed model with existing IR designs is made using a simulation study.
The Portable parallel/distributed Debugger project at the NASA Ames Research Center has built a debugger for applications running on heterogeneous computational grids. It employs a client-server architecture to simpli...
详细信息
The Portable parallel/distributed Debugger project at the NASA Ames Research Center has built a debugger for applications running on heterogeneous computational grids. It employs a client-server architecture to simplify the implementation, and its user interface has been designed to provide process control and state examination functions on computations with a large number of processes. The debugger can find processes participating in distributed computations even when those processes were not created under debugger control. In addition to working in a computational grid environment, these techniques also work on other distributed memory jobs, such as those initiated by "mpirun".
Introduces and evaluates a new efficient dynamic load-balancing scheme for parallel molecular dynamics simulation on distributed memory machines. It decomposes a spatial domain of particles into disjoint parts, each o...
详细信息
Introduces and evaluates a new efficient dynamic load-balancing scheme for parallel molecular dynamics simulation on distributed memory machines. It decomposes a spatial domain of particles into disjoint parts, each of which corresponds with a processor and dynamically changes its shape to keep almost the same number of particles throughout simulation. In contrast to other similar schemes, ours requires no long-distance inter-processor communications but only those among adjacent processors (and, thus, little communication overhead), whereas it still guarantees fast reduction of load imbalance among the processors. It owes these advantages mainly to the following features. (1) The sufficiently correct global load information is effectively obtained with the stepwise propagation of appropriate information via nearest-neighbor communication. (2) In addition to the global load balancing, another load-balancing procedure is also invoked on each processor without global load information in order to suppress the rapid increase or decrease of loads. Thus, information from remote processors can provide reliable values even after a certain period of delay. To evaluate the effectiveness of our scheme, we have integrated our load balancer into the publicly-available NAMD simulation system, through replacing its built-in load-balancing component. Preliminary experiments on a cluster of workstations connected through Myrinet switches shows that it successfully reduces load imbalance and improves the simulation performance.
暂无评论