Connectionist models, often known as artificial neural networks, are currently the subject of a tremendous rebirth of interest in various domains of applications. These models employ massively parallel networks of sim...
详细信息
ISBN:
(纸本)0852965192
Connectionist models, often known as artificial neural networks, are currently the subject of a tremendous rebirth of interest in various domains of applications. These models employ massively parallel networks of simple processing elements in order to capture some knowledge of the external world as distributed patterns of activation across their nodes. A few designers have implemented neural networks directly in special-purpose VLSI hardware following the inherent parallelism of the model and offering high speed-up over simulation and serial machines. The implementation of multilayered neural networks on two parallel architectures are studied: the Connection Machine, a SIMD type computer, and the TNode, a Transputer based MIMD computer. Various implementations are compared and experimental results and performance evaluations are presented.
The proceedings contain 41 papers. The special focus in this conference is on Algorithms. The topics include: Decision-making with incomplete information;maximum independent set of a permutation graph in k tracks;algo...
ISBN:
(纸本)9783540549451
The proceedings contain 41 papers. The special focus in this conference is on Algorithms. The topics include: Decision-making with incomplete information;maximum independent set of a permutation graph in k tracks;algorithms for square roots of graphs;distributed k-mutual exclusion problem and k-coteries;weighted random assignments with application to hashing;scheduling file transfers under port and channel constraints;substitution decomposition on chordal graphs andapplications;mixed-searching and proper-path-width;short wire routing in convex grids;a new approach to knock-knee channel routing;an average case analysis of monien and speckenmeyer's mechanical theorem proving algorithm;an on-line algorithm for navigating in unknown terrain;on maintaining the width and diameter of a planar point-set online;optimal triangulations by retriangulating;an incremental algorithm for constructing shortest watchman routes;on hitting grid points in a convex polygon with straight lines;on the complexity of some hamiltonian and eulerian problems in edge-colored complete graphs;dynamic programming on intervals;combinatorial optimization through order statistics;combinatorics and algorithms of geometric arrangements;an analysis of randomized shear sort on the mesh computer;efficient parallel divide-and-conquer for a class of lnterconnection topologies;optimal specified root embedding of full binary trees in faulty hypercubes;a tight lower bound for the worst case of bottom-up heapsort;historical searching and sorting;comparison-efficient and write-optimal searching and sorting;nearest neighbors revisited;competitiveness and response time in on-line algorithms;a linear time optimal via assignment algorithm for three-dimensional channel routing;symmetry of information and one-way functions.
The paper considers the problem of constructing a planer orthogonal grid drawing (or more simply, layout) of an n-vertex graph, with the goal of minimizing the number of bends along the edges. It exhibits graphs that ...
详细信息
Increasing use of hypercube systems in reliability-critical applications has made fault-tolerant communication algorithms for hypercube important. This paper describes four fault-tolerant routing algorithms for hyperc...
详细信息
Increasing use of hypercube systems in reliability-critical applications has made fault-tolerant communication algorithms for hypercube important. This paper describes four fault-tolerant routing algorithms for hypercubes subject to link failures, namely any/sub -/nd, sidewalk, lookahead and lookside. The principle of sidewalk and lookahead are similar to two existing approaches. Lookside is an improved version of either of them. Sidewalk, lookahead and lookside guarantee successful routing in a d-cube if the number of link failures is less than d. For higher degree of link failures, the authors measure their performance by probability of successful routing and expected routing distance using two fault distribution models, probability fault model and random fault model. Lookside demonstrates better properties than sidewalk and lookahead in that it has the highest successful routing rate with reasonable routing distance.< >
The paper considers the problem of constructing a planer orthogonal grid drawing (or more simply, layout) of an n-vertex graph, with the goal of minimizing the number of bends along the edges. It exhibits graphs that ...
详细信息
The paper considers the problem of constructing a planer orthogonal grid drawing (or more simply, layout) of an n-vertex graph, with the goal of minimizing the number of bends along the edges. It exhibits graphs that require Omega (n) bends in any layout, and shows that there exist optimal drawings that require Omega (n) bends and have all of them on a single edge of length Omega (n/sup 2/). On the other side of the coin, it presents a parallel algorithm that runs on a CREW PRAM in O(log n) time with n/log n processors and constructs layouts with O(n) maximum edge length and O(n/sup 2/) area. for biconnected graphs the number of bends is at most 2n+4, which is optimal in the worst-case. This work finds applications in VLSI layout, aesthetic graph drawing, and communication by light or microwave.< >
Connected components detection and labeling is an essential step in many image analysis techniques. The efficiency of the connected components labeling algorithm is critical for many image processing and machine visio...
详细信息
Connected components detection and labeling is an essential step in many image analysis techniques. The efficiency of the connected components labeling algorithm is critical for many image processing and machine vision applications that require real time response. The advances in the areas of parallelprocessing and VLSI technology can be exploited in designing hardware algorithms of high speed and throughput. The authors propose a systolic algorithm and architecture for finding connected components in an image. The architecture is simple and can be implemented as a special purpose VLSI chip. Although, the algorithm has a time complexity of O(N/sup 2/), this is in terms of the actual clock cycle which is estimated as 25 nano seconds. The proposed hardware can process a 128*128 image on 0.85 msec and uses 128 processors where as the MPP requires 94.6 msec with 16384 processors. The only special purpose hardware that exists due to X.D. Yang (1988) requires 300 msec to label a 512*512 image which can be accomplished in about 13.5 msec using the authors' proposed hardware.< >
In this paper we introduce and discuss a model of distributed data processing. For this purpose, a typical application system is analyzed and divided into sub-applications. To fulfill the task of the global applicatio...
详细信息
ISBN:
(纸本)0818620528
In this paper we introduce and discuss a model of distributed data processing. For this purpose, a typical application system is analyzed and divided into sub-applications. To fulfill the task of the global application, the sub-applications have to communicate in an appropriate manner by exchanging data resp. information. In our model the communication between sub-applications is split up into two steps: the offering of information by sending sub-applications, and its acceptance by receiving sub-applications. For both communication steps synchronous and asynchronous processing modes are defined. Supporting those different communication modes the cooperation between sub-applications can be defined very closely to the specific demands of the application system. This optimizes distributed data processing. At last we demonstrate the prototype implementation of a distributed data management system, which is based on the flexible communication mechanism described in the paper.
distributed shared memory (DSM) has received increased attention as a mechanism for interprocess communication in loosely-coupled distributed systems because of its perceived advantages over direct use of message pass...
详细信息
The problem of packing adjustable rectangles into a rectangular bin with minimum height is investigated. In this problem, the length and width of each rectangle can be changed, based on certain reshaping rules, before...
详细信息
For a database system executing on a multiprocessor system, performance can be improved by inter-query parallelism as well as by intra-query parallelism. Since database applications tend to be 1/0 bound, it is importa...
详细信息
暂无评论