Consider an array of Processing Elements [PEs], connected by a 2-dimensional grid network, and holding at most one operand of an expression in each PE. Suppose that each PE is allowed, in any one parallel step, to receive one item of data from any of its four immediate neighbors, and to transmit one datum, as well. How can an associative operator, such as addition, combine all the operands, using as little time for communciation as possible? An expression using such a single operator is termed a uniform expression. When the total number of communication links used is the measure of goodness, this problem becomes a Steiner Tree problem, in the Manhattan Distance metric. When the measure is minimizing the parallel time to completion, a method for solving this problem is given which is optimal to within an additive constant of two time-steps. The method has applications when the operands are matrices, spread over an array of PEs, as well. Some lower bounds for this problem, in more general networks, are also proven.

A parallel algorithm for computing the connected components of undirected graphs is presented. Shared memory computation models are assumed. For a graph of e edges and n nodes, the time complexity of the algorithm is Ο( e/p + ( n log n )/ p + log 2 n ) with p processors. The algorithm can be further refined to yield time complexity Ο( H ( e , n , p )/ p + ( n log n )/( p log( n / p )) + log 2 n ), where H ( e, n, p ) is very close to Ο( e ). These results show that linear speedup can be obtained for up to p ≤ e /log 2 n processors when e ≥ n log n . Linear speedup can still be achieved with up to p ≤ n ε processors, 0 ≤ ε < 1, for graphs satisfying e ≥ n log (*) n . Our results can be further improved if a more efficient integer sorting algorithm is available.

Article Free Access Share on Combining speed with alpha-particle induced memory, error tolerance in a large boolean vector machine Authors: Richard M. King Kestrel Institute, 1801 Page Mill Road, Palo Alto, CA Kestrel Institute, 1801 Page Mill Road, Palo Alto, CAView Profile , Robert A. Wagner Duke University, Dept. of Computer Science, Durham, NC Duke University, Dept. of Computer Science, Durham, NCView Profile Authors Info & Claims ISCA '84: Proceedings of the 11th annual international symposium on Computer architectureJanuary 1984 Pages 251–253https://doi.org/10.1145/800015.808192Online:01 January 1984Publication History 0citation182DownloadsMetricsTotal Citations0Total Downloads182Last 12 Months1Last 6 weeks0 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my Alerts New Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

We describe the architecture of a class of machines intended to solve computationally intensive problems much faster than can today's machines, at no increase in cost. We have investigated the programming of the BVM for several interesting algorithms on a BVM of 2k bit positions per register. More theoretical study of implementations of such highly parallel algorithms is motivated.

article Free Access Share on Optimal Selection of CPU Speed, Device Capacities, and File Assignments Authors: Kishor S. Trivedi Department of Computer Science, Duke University, Durham, NC Department of Computer Science, Duke University, Durham, NCView Profile , Robert A. Wagner Department of Computer Science, Duke University, Durham, NC Department of Computer Science, Duke University, Durham, NCView Profile , Timothy M. Sigmon Department of Computer Science, Duke University, Durham, NC Department of Computer Science, Duke University, Durham, NCView Profile Authors Info & Claims Journal of the ACMVolume 27Issue 3July 1980 pp 457–473https://doi.org/10.1145/322203.322208Published:01 July 1980Publication History 44citation552DownloadsMetricsTotal Citations44Total Downloads552Last 12 Months35Last 6 weeks1 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my Alerts New Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

This paper considers a computer configuration design problem. The computer system is modeled by a closed queuing network. The system throughput is the objective function to be maximized and the speed of the devices are the decision variables. A rich class of non-linear cost functions is considered.

Correction of a string x into a language L is the problem of finding a string $y \in L$ to which x can be edited at least cost. The edit operations considered here are single-character deletions, single-character insertions, and single-character substitutions, each at an independent cost that does not depend on context. Employing a linear-time algorithm for solving single-origin graph shortest distance problems, it is shown how to correct a string of length n into the language accepted by a counter automaton in time proportional to $n^2 $ on a RAM with unit operation cost function. The algorithm is uniform over counter automata and edit cost functions; and it is shown how the correction time depends on the size of the automaton, the nature of the cost function, and the correction cost itself. For less general cases, potentially faster algorithms are described, including a linear-time algorithm for the case that very little correction is necessary and that the automaton’s counter activity is determined by the input alone. Specializing the main result to counter automata which do not use their counters gives general linear-time correction into regular languages.

An algorithm ( FLOW ) for finding the shortest distance from a given node S to each node X of a directed graph with nonnegative integer arc lengths less than or equal to WM is presented. FLOW is compared with its best-known competitor, that of Dijkstra and Yen ( DFLO ). The new algorithm is shown to execute in time of order max ( V, E, D ), where D is the maximum distance computed in a graph with E edges and V nodes. By counting the number of operands fetched during execution of FLOW and DFLO , an estimate of the running time of each is obtained. This estimate shows that FLOW should execute faster than DFLO when E / V 2 = α < .2875, and V ≥ 22 WM / β + 5/ β + 7.04, where β = 23 - 80 α . FLOW also will solve the all-pairs shortest distance problem, requiring time O ( V * max( V, E, D )) for the solution.

The Extended String-to-String Correction Problem [ESSCP] is defined as the problem of determining, for given strings A and B over alphabet V, a minimum-cost sequence S of edit operations such that S(A) = B. The sequence S may make use of the operations: Change, Insert, Delete and Swaps, each of constant cost WC, WI, WD, and WS respectively. Swap permits any pair of adjacent characters to be interchanged. The principal results of this paper are: (1) a brief presentation of an algorithm (the CELLAR algorithm) which solves ESSCP in time O(¦A¦* ¦B¦* ¦V¦s*s), where s = min(4WC, WI+WD)/WS + 1; (2) presentation of polynomial time algorithms for the cases (a) WS = 0, (b) WS > 0, WC= WI= WD=

The string-to-string correction problem asks for a sequence S of "edit operations" of minimal cost such that ~(A) = B, for given strings A and B. The edit operations previously investigated allow changing one symbol of a string into another single symbol, deleting one symbol from a string, or inserting a single symbol into a string.This paper extends the set of allowable edit operations to include the operation of interchanging the positions of two adjacent characters Under certain restrictions on edit-operation costs, it is shown that the extended problem can still be solved in time proportional to the product of the lengths of the given strings.

The string-to-string correction problem is to determine the distance between two strings as measured by the minimum cost sequence of “edit operations” needed to change the one string into the other. The edit operations investigated allow changing one symbol of a string into another single symbol, deleting one symbol from a string, or inserting a single symbol into a string. An algorithm is presented which solves this problem in time proportional to the product of the lengths of the two strings. Possible applications are to the problems of automatic spelling correction and determining the longest subsequence of characters common to two strings.

Abstract An algorithm for solving the Steiner problem on a finite undirected graph is presented. This algorithm computes the set of graph arcs of minimum total length needed to connect a specified set of k graph nodes. If the entire graph contains n nodes, the algorithm requires time proportional to n 3 /2 + n 2 (2 k‐1 ‐ k ‐ 1) + n(3 k‐1 ‐ 2 k + 3)/2. The time requirement above includes the term n 3 /2, which can be eliminated if the set of shortest paths connecting each pair of nodes in the graph is available.