The proceedings contain 48 papers. The special focus in this conference is on Algorithms. The topics include: *** progress in string algorithms;parallel algorithms for linked list and beyond;local tournaments and prop...
ISBN:
(纸本)9783540529217
The proceedings contain 48 papers. The special focus in this conference is on Algorithms. The topics include: *** progress in string algorithms;parallel algorithms for linked list and beyond;local tournaments and proper circular arc graphs;fast algorithms for the dominating set problem on permutation graphs;two probabilistic results on merging;randomized broadcast in networks;on the construction of abstract voronoi diagrams, II;searching in higher dimension;finding extrema with unary predicates;implicitly searching convolutions and computing depth of collision;characterization for a family of infinitely many irreducible equally spaced polynomials;selection networks;distributed algorithms for deciphering;an efficient algorithm for optimal loop parallelization;another view on the SSS* algorithm;algorithms from complexity theory: Polynomial-time operations for complex sets;complexity cores and hard problem instances;spatial point location and its applications;sublinear merging and natural merge sort;constructing strongly convex approximate hulls with inaccurate primitives;computing puiseux-series solutions to determentantal equations via combinatorial relaxation;a tight lower bound on the size of planar permutation networks;computing edge-connectivity in multiple and capacitated graphs;simultaneous solution of families of problems;algorithms for projecting points to give the most uniform distribution with applications to hashing;topological sweeping in three dimensions;finding least-weight subsequences with fewer processors;derandomization by exploiting redundancy and mutual independence;planar separators and the euclidean norm;on the complexity of isometric embedding in the hypercube;distributed function evaluation in the presence of transmission faults;optimal linear broadcast;graph augmentation problems for a specified set of vertices.
A Spanning Balancedn-tree (SBnT) in a Boolean n-cube is a spanning tree in which the root has fanout n, and all the subtrees of the root have $O({{2^n } / n})$ nodes. The number of tree edges in each dimension of the ...
详细信息
A Spanning Balancedn-tree (SBnT) in a Boolean n-cube is a spanning tree in which the root has fanout n, and all the subtrees of the root have $O({{2^n } / n})$ nodes. The number of tree edges in each dimension of the n-cube is of order $O({{2^n } / n})$. The spanning balanced n-tree allows for scheduling disciplines that realize lower bound (within a factor of two) one-to-all personalized communication, all-to-all broadcasting, and all-to-all personalized communication on a Boolean n-cube [C.-T. Ho and S. L. Johnsson, Proc. 1986 internationalconference on Parallel Processing, pp. 640–648, IEEE Computer Society, 1986; Tech. Report YALEU/DCS/RR–483, May 1986], [S. L. Johnsson and C.-T. Ho, Tech. Report YALEU/DCS/RR–610, Dept. of Computer Science, Yale Univ., New Haven, CT, November 1987]. The improvement in data transfer time over the familiar binomial tree routing is a factor of ${n / 2}$ for concurrent communication on all ports and one-to-all personalized communication and all-to-all broadcasting. For all-to-all personalized communication on all ports concurrently, the improvement is of order $O(\sqrt n )$. distributed routing algorithms defining the spanning balanced n-tree are given. The balanced n-tree is not unique, and a few definitions of n-trees that are effectively edge-disjoint are provided. Some implementation issues are also discussed.
A compositional proof system is given for an OCCAM-like real-time programming language for distributedcomputing with communication via synchronous message passing. This proof system is based on specifications of proc...
详细信息
The proceedings contain 55 papers. The special focus in this conference is on Parallel Architectures and Languages Europe. The topics include: An implemented method for incremental systolic design;the use of parallel ...
ISBN:
(纸本)9783540179436
The proceedings contain 55 papers. The special focus in this conference is on Parallel Architectures and Languages Europe. The topics include: An implemented method for incremental systolic design;the use of parallel functions in system design;the translation of processes into circuits;mapping strategies in message based multiprocessor systems;hardware memory management for large knowledge bases;Transputer-based experiments with the ZAPP architecture;synthesis of systolic arrays for inductive problems;practical parallelism using transputer arrays;systolic array synthesis by static analysis of program dependencies;trace theory and systolic computations;Specification of a pipelined event driven simulator using FP2;A layered emulator for design evaluation of MIMD multiprocessors with shared memory;The Alliant FX/Series: A language driven architecture for parallel processing of dusty deck fortran;emulating digital logic using transputer networks (very high parallelism = simplicity = performance);a two-level approach to logic plus functional programming integration;overview of a parallel reduction machine project;An overview of DDC: Delta driven computer;design and implementation of a parallel inference machine for first order logic: An overview;Multi-level simulator for VLSI: An overview;The DOOM system and its applications: A survey of esprit 415 subproject A, philips research laboratories;boltzmann machines and their applications;COBWEB-2: structured specification of a wafer-scale supercomputer;a novel deadlock free and starvation free packet switching communication processor;a parallel architecture for signal understanding through inference on uncertain data;an axiomatic approach to the specification of distributed computer architectures;computing on a systolic screen: Hulls, contours and applications.
The proceedings contain 55 papers. The special focus in this conference is on Parallel Architectures and Languages Europe. The topics include: An implemented method for incremental systolic design;the use of parallel ...
ISBN:
(纸本)9783540179450
The proceedings contain 55 papers. The special focus in this conference is on Parallel Architectures and Languages Europe. The topics include: An implemented method for incremental systolic design;the use of parallel functions in system design;the translation of processes into circuits;mapping strategies in message based multiprocessor systems;hardware memory management for large knowledge bases;Transputer-based experiments with the ZAPP architecture;synthesis of systolic arrays for inductive problems;practical parallelism using transputer arrays;systolic array synthesis by static analysis of program dependencies;trace theory and systolic computations;Specification of a pipelined event driven simulator using FP2;A layered emulator for design evaluation of MIMD multiprocessors with shared memory;The Alliant FX/Series: A language driven architecture for parallel processing of dusty deck fortran;emulating digital logic using transputer networks (very high parallelism = simplicity = performance);a two-level approach to logic plus functional programming integration;overview of a parallel reduction machine project;An overview of DDC: Delta driven computer;design and implementation of a parallel inference machine for first order logic: An overview;Multi-level simulator for VLSI: An overview;The DOOM system and its applications: A survey of esprit 415 subproject A, philips research laboratories;boltzmann machines and their applications;COBWEB-2: structured specification of a wafer-scale supercomputer;a novel deadlock free and starvation free packet switching communication processor;a parallel architecture for signal understanding through inference on uncertain data;an axiomatic approach to the specification of distributed computer architectures;computing on a systolic screen: Hulls, contours and applications.
The following topics are dealt with: windowing techniques;display architecture;user interface;operating systems and architecture;benchmarking and performance;applications;CAD applications;distributed systems;workstati...
详细信息
ISBN:
(纸本)0818606495
The following topics are dealt with: windowing techniques;display architecture;user interface;operating systems and architecture;benchmarking and performance;applications;CAD applications;distributed systems;workstation computing environment;workstation architectures;RISC architecture for workstations;the Apollo environment;role of microcomputers. 38 papers were presented, of which 37 are published in full in the present proceedings.
The Xerox Palo Alto Research Center (PARC) has established an integrated-circuit process characterization facility within its Integrated Circuit Laboratory (ICL) based upon a distributedcomputing environment comprisi...
详细信息
ISBN:
(纸本)0818606495
The Xerox Palo Alto Research Center (PARC) has established an integrated-circuit process characterization facility within its Integrated Circuit Laboratory (ICL) based upon a distributedcomputing environment comprising Xerox workstations and Xerox development software integrated through the use of the Xerox Research Ethernet. The ramifications of this distributed approach to integrated-circuit fabrication are discussed. As examples of the superiority of this approach, the development of two parametric testing systems, automated extraction of MOS capacitor and CMOS latch-up parameters, are described in the context of this distributed workstation environment.
The need that people (and computer systems) in an organization have for data sharing is categorized. This categorization forms a spectrum of sharing requirements which includes only the most casual sharing at one extr...
详细信息
ISBN:
(纸本)0818606495
The need that people (and computer systems) in an organization have for data sharing is categorized. This categorization forms a spectrum of sharing requirements which includes only the most casual sharing at one extreme (dealt with in many computing shops by tape copy), and continuous and effortless intimate sharing on the other (formerly available only through the use of monolithic time-sharing systems). Orthogonal to the sharing requirements of a particular computing environment is the need to deal with heterogeneous computing systems (heterogeneous with respect to both manufacturer and operating system) within the computing environment. The issue of sharing, the points on the sharing requirements spectrum and the special support needed to deal with heterogeneity are examined.
暂无评论