A simple and effective parallel algorithm to color the nodes of a graph is presented. the algorithm is useful in its own right. It also provides a vehicle to demonstrate the tradeoffs between performance and speed imp...
详细信息
ISBN:
(纸本)081860865X
A simple and effective parallel algorithm to color the nodes of a graph is presented. the algorithm is useful in its own right. It also provides a vehicle to demonstrate the tradeoffs between performance and speed implicit in many parallel algorithms. the algorithm is used when the parallel machine has at least as many processors as there are nodes to color.
A description is given of a novel concept and mechanism, called an object group, that realizes hierarchical, integrated object processing and management. Object groups can be used as a software basis for constructing ...
详细信息
ISBN:
(纸本)081860865X
A description is given of a novel concept and mechanism, called an object group, that realizes hierarchical, integrated object processing and management. Object groups can be used as a software basis for constructing object-based distributed systems. they support hierarchical control of objects, group-oriented communications, group access control, group resource management, and some generic operations on groups, providing consistent and uniform interfaces. Applications include job control, parallelprocessing, servers, object pools, hierarchical resource management, and so on. Some design issues are presented, and an implementation on a network-transparent global distributed system, which is under development, is discussed.
the authors present the design, implementation, and testing of the critical path analysis technique using the IPS performance measurement tool for parallel and distributed programs. they create a precedence graph of a...
详细信息
ISBN:
(纸本)081860865X
the authors present the design, implementation, and testing of the critical path analysis technique using the IPS performance measurement tool for parallel and distributed programs. they create a precedence graph of a program's activities (program activity graph) withthe data collected during the execution of a program. the critical path, the longest path in the program activity graph, represents the sequence of the program activities that take the longest time to execute. Various algorithms are developed to track the critical path from this graph. the events in this path are associated withthe entities in the source program, and the statistical results are displayed on the basis of the hierarchical structure of the IPS. the test results from the measurement of sample programs show that the knowledge of the critical path in a program's execution helps users identify performance problems and better understand the behavior of a program.
A parallel file system called Bridge that distributes each file across multiple storage devices and processors has been designed and prototyped. the approach is based on the notion of an interleaved file, in which con...
详细信息
ISBN:
(纸本)081860865X
A parallel file system called Bridge that distributes each file across multiple storage devices and processors has been designed and prototyped. the approach is based on the notion of an interleaved file, in which consecutive logical blocks are assigned to different physical nodes. Naive programs are able to access files just as they would with a conventional file system, while more sophisticated programs can export pieces of their code to the processors managing the data, for optimum performance. Early analytical and experimental results indicate that Bridge will deliver good parallel speedup for configurations in excess of 32 nodes with disks. High performance is achieved by exporting the I/O-related portions of an application into the processors closest to the data. A pair of applications that illustrate this technology is presented. General issues in the design of algorithms for Bridge are discussed.
Multiprocessor architectures using point-to-point interconnects and executing parallel algorithms require careful partitioning and allocation of data and processes. For a given interconnection, optimal allocation may ...
详细信息
ISBN:
(纸本)081860865X
Multiprocessor architectures using point-to-point interconnects and executing parallel algorithms require careful partitioning and allocation of data and processes. For a given interconnection, optimal allocation may be difficult to achieve in some cases because the data-dependent behavior of some algorithms may be impossible to predict. A mechanism called the pivot mechanism is introduced and described that controls the dynamic migration of data pages between neighboring memory modules during program execution. Flexible data migration serves the dual purpose of making algorithms less machine-specific and making possible efficient algorithm execution that is impossible to achieve by using static data allocation.
Systems that have the capability of executing tasks with various sizes and computation structures simultaneously are considered. When some of the tasks are completed, part of the system becomes idle and is reconfigure...
详细信息
ISBN:
(纸本)081860865X
Systems that have the capability of executing tasks with various sizes and computation structures simultaneously are considered. When some of the tasks are completed, part of the system becomes idle and is reconfigured for new tasks. Inappropriate reconfiguration strategies can create resource fragments and result in a loss of computation power. this problem can be alleviated by partitioning the system dynamically. Partitioning consists of two processes: splitting the system or a subsystem into smaller subsystems, and combining unallocated subsystems into larger subsystems. these two processes are investigated analytically for a lattice model that uses a special partial ordering relation on a set. the complexities of these two processes are also analyzed. the method can be applied to any system that can be modeled by a lattice.
A distributed data structure Is a data structure that can be manipulated by many paralisi processes simultaneously. distributed data structures are the natural complement to parallel program structures, where a parall...
详细信息
ISBN:
(纸本)089791175X
A distributed data structure Is a data structure that can be manipulated by many paralisi processes simultaneously. distributed data structures are the natural complement to parallel program structures, where a parallel program (for our purposes) is one that is made up of many simultaneously active, communicating processes. distributed data structures are impossible in most parallel programming languages, but they are supported In the parallel language Linda and they are central to .Linda programming style. We outline Linda, then discuss some distributed data structures that have arisen In Linda programming experiments to date. Our intent is neither to discuss the design of the Linda system nor the performance of Linda programs, though we do comment on both topics;we are concerned instead with a few of the simpler and more basic techniques made possible by a language model that, we argue, is subtly but fundamentally different in its implications from most others.
In this paper, we propose and analyze the design of MANIP, a parallel machine for processing nondeterministic polynomial complete problems. the most general technique that can be used to solve a wide variety of NP-com...
详细信息
Multicomputer systems withdistributed control form an architecture that simultaneously satisfies such design goals as high performance through parallel operation of VLSI processors, modular extensibility, fault toler...
详细信息
暂无评论