leff@smu.UUCP (Laurence Leff) (04/22/88)
TECHNICAL REPORTS FOR 1986 Computer and Information Science Department University of Oregon Eugene, OR 97403 CIS-TR-86-01 Parallel Computation and the NC Hierarchy Relativized by Christopher B. Wilson. Abstract: In this paper we construct oracles which allow us to compare complexity classes defined in terms of sequential resource measures to those defined in terms of parallel ones. It is known in the unrelativized case that NC sub 1 ~ !subset ~ L~ !subset ~NL~ !subset ~NC sub 2 ~ !subset ~ ... ~ !subset ~NC~ !subset ~P but none of these containments is known to be strict. First we introduce a natural model of relativized depth. It is shown that NC sub 1 subset L if and only if exist ~ A, NC sub 1 sup A subset L sup A, where subset denotes strict containment. We then exhibit oracles B and C with NC sub 1 sup B = NC sub 2 sup B = P sup B and NC sub 1 sup C ~ subset ~NC sub 2 sup C ~ subset ~ ... Relativized depth is shown to be potentially powerful as there is a D such that for ~k, NC sub 1 sup D ~-~ NSPACE sup D (n sup k ) is nonempty. Finally, a new model of relativized space is proposed which is shown to retain most properties that hold in the unrelativized case. CIS-TR-86-02 Closed Environments: Partitioned Memory Representation for Parallel Logic Programs by John S. Conery. Abstract: An implementation technique for parallel logic programs is described. Variable bindings are stored in many small independent environments, with minimal sharing of information, unlike Prolog's three-stack representation which depends heavily on pointers from one activation record to another. The independent environments may be stored in different memories; a single global memory space is not required. Use of the new scheme is illustrated in the context of two parallel interpreters. CIS-TR-86-03 Parallel Algorithms for Permutation Groups and Graph Isomorphism by Eugene M. Luks. Abstract: We develop parallel techniques for dealing with permutation group problems. These are most effective on the class of groups with bounded non-albelian composition factors. For this class, we place in NC problems such as membership testing, finding the center and composition factors, and, of particular significance, finding pointwise-set-stabilizers. The last has applications to instances of graph-isomorphism and we show that NC contains isomorphism-testing for vertex-colored graphs with bounded color multiplicity, a problem not long known to be in polynomial time. CIS-TR-86-04 Artifacts at the Limit of Resolution by Kent A. Stevens and Daniel P. Lulich. Abstract: A visual illusion which appears at the limit of resolution is used to investigate perceived artifacts of the convolution by Gaussian filters. Evidence is provided that implicate the smallest size operator at the retina and that suggest that the perceived shape of intensity changes is influenced by artifacts induced by the operator. CIS-TR-86-05 Integrating Stereopsis with Monocular Interpretations of Planar Surfaces by Kent A. Stevens and Allen Brookes. Abstract: In a series of experiments in which stereo and monocular 3D interpretations were made mutually inconsistent, stereopsis was found to integrate with monocular depth only when disparities varied nonlinearly spatially. The apparent spatial disposition, including local surface orientation and depth ordering, was dominated by the monocular interpretation, even when stereo information provided strongly contradictory information. We conclude that stereo and monocular vision is integrated primarily on the basis of topographic features, not scalar depth values. Moreover, in interpreting depth from stereograms, we found a stereoscopic analogue to the familiar brightness contrast effect. The depth interpretation of stereo disparity information is roughly analogous to edge detection, with insensitivity to constant disparity gradients analogous to our insensitivity to linear (ramp-like) intensity distributions. This rules out several current models of spatial integration, and suggests new computational strategies. CIS-TR-86-06 Probing Depth in Monocular Images by Kent A. Stevens and Allen Brookes. Abstract: It is generally expected that depth (distance) is the internal representational primitive that corresponds to much of the perception of 3D. We tested this assumption in monocular surface stimuli that are devoid of distance information (due to orthographic projection and the chosen surface shape, with perspective projection used as a control) and yet are vividly three-dimensional. Slant judgments were found to be in close correspondence with the actual geometric slant of the stimuli; the spatial orientation of the surfaces was perceived accurately. The apparent depth in these stimuli was then tested by superimposing a stereo depth probe over the monocular surface. In both the perspective and orthographic project the gradient of perceived depth, measured by matching the apparent depth of the stereo probe with that of the monocular surface at a series of locations, was substantial. The experiments demonstrate that in orthographic projection the visual system can compute from local surface orientation a depth quantity that is commensurate with the relative depth derived from stereo disparity. The depth data suggests that, at least in the near field, the zero value for relative depth lies at the same absolute depth, as the stereo horopter (locus of zero stereo disparity). Relative to this zero value, the depth-from-slant computation seems to provide an estimate of distance information that is independent of the absolute distance to the surface. CIS-TR-86-07 Forbidden Minors Characteriziation of Partial 3-trees by Andrzej Proskurowski, Stefan Arnborg, and Derek Corneil. Abstract: A k-tree is formed from a k-complete graph by recursively adding a vertex adjacent to all vertices in an existing k-complete subgraph. The many applications of partial k-trees (subgraphs of k-trees) have motivated their study from both the algorithmic and theoretical points of view. In this paper we characterize the class of partial 3-trees by its set of four minimal forbidden minors (H is a minor of G if H can be obtained from G by a finite sequence of edge-extraction and edge-contraction operations). .bp CIS-TR-86-08 Automating the Analysis Process: An Example by Stephen Fickas. Abstract: Our goal is the automation of the requirements analysis process using a problem solving approach. In this paper we discuss a) the components of our ideal system, b) the test of a smaller demonstration system on problem #1 from the workshop problem set, and c) our prescription for further work in the area. CIS-TR-86-09 Backward Execution in Nondeterministic AND-Parallel Systems by John Conery. Abstract: A new algorithm for ``backward execution'' in AND-parallel logic programs is described, and new implementation techniques for this class of algorithm are introduced. The dataflow graph that determines forward and backward execution orders, the status of subgoals, and other state information in an AND process are represented by bitsets, and the steps of the algorithm are efficient operations on bitsets. Data from simulations show the implementation techniques are effective, and form the basis of several interesting future experiments. CIS-TR-86-10 Detecting Structure by Symbolic Constructions on Tokens by Kent A. Stevens and Allen Brookes. Abstract: Geometric organization is readily detected in discrete textures such as dot patterns. A common proposal is that orientation-tuned receptive field mechanisms provide the local orientation information from which the global organizations emerge. Alternatively, the local orientation might be attributed to grouping constructions between adjacent tokens, each representing the position of a dot and its attributes such as color, size and contrast. Geometric organization would then emerge by grouping operations on selected tokens that are similar, adjacent and aligned. It is the ability to group on the basis of similarity that most strongly differentiates this from the energy-summating receptive field approach. Using dot patterns with rivalrous organization, we demonstrate grouping phenomena that are difficult to attribute to a broad class of energy summation detectors operating in the spatial frequency domain, which we therefore attribute to perceptual groupings on tokens. We discuss the computational differences between feature detection and structure detection, and suggest that orientation-tuned receptive field mechanisms, while appropriate for the former task, have little application to the latter. CIS-TR-86-12 Synthesizing Systolic Arrays with Control Signals from Recurrence Equations by Sanjay V. Rajopadhye and Richard M. Fujimoto. Abstract: We present a technique for synthesizing systolic arrays which have non-uniform data flow governed by control signals. The starting point of the synthesis process is a Recurrence Equation with Linear Depencencies (RELD) which is a generalization of the simple recurrences encountered in mathematics. The process of synthesis consists of three stages. Since such a recurrence defines a dependency graph similar to a program dependency graph, the first stage involves the determination of a linear schedule (also called an affine timing function) and a linear allocation function for the RELD. The second stage consists of explicitly pipelining the dependencies so that the data flow is guaranteed to be localized. We present a unified theory for this pipelining process and show that it yields recurrences that have linear conditional expressions governing the computation. The third step naturally follows from this and consists of deriving control signals from the linear conditional expressions. The approach is illustrated by deriving the Guibas-Kung-Thompson architecture for optimum string parenthesization. CIS-TR-86-13 Heuristic Algorithms for Task Assignment in Distributed Computing Systems by Virginia M. Lo. Abstract: In this paper we investigate the problem of task assignment in distributed computing systems, i.e., given a set of k communicating tasks to be executed on a distributed system of n processors, to which processor should each task be assigned? We propose a family of heuristic algorithms for Stone's classic model of communicating tasks which considers the execution cost of each task on each processor and the communication costs between tasks. We augment this model to include interference costs which reflect the degree of incompatibility between two tasks. Whereas high communication costs serve as a force of attraction between tasks, causing them to be assigned to the same processor, interference costs serve as a force of repulsion between tasks, causing them to be distributed over many processors. The inclusion of interference costs in the model yields assignments with greater concurrency thus overcoming the tendency of Stone's model to assign all tasks to one or a few processors. Simulation results show that our algorithms perform well and in particular, that the highly efficient Simple Greedy Algorithm performs almost as well as more complex heuristic algorithms. When we consider task assignment to be an initial placement of tasks subject to subsequent refinement by dynamic task migration algorithms, efficient algorithms such as Simple Greedy are attractive candidates for practical distributed systems. If task assignment modules make a permanent assignment of tasks to processors, the increased overhead of a more complex heuristic is justified for the improvement in the assignment. CIS-TR-86-14 Intelligent Scheduling in Distributed Computing Systems by Virginia M. Lo and David Chen. Abstract: Our research into the problem of scheduling in distributed computing systems indicates that several techniques and tools from the area of ``expert systems'' can be successfully adapted for use in the design of a smart distributed scheduler. In this paper we look at expert system approaches to the representation of imprecise knowledge, techniques for reasoning about imprecise and unreliable knowledge, and means for handling knowledge accumulated over time. We show that that these are precisely the types of knowledge a distributed systems scheduler must deal with in order to make scheduling decisions and we give examples of the use of these techniques in the realm of task assignment and task migration algorithms. We then describe a task migration algorithm we have designed which utilizes rule based programming and expert systems techniques to deal with out-of-date and thus potentially unreliable data in system load tables. CIS-TR-86-16 Finding a Minimum Base for Permutation Groups is NP-hard by Kenneth D. Blaha. Abstract: The notions of a base and strong generating set were defined by Sims in 1970, and used as an efficient method to store and analyze large permutation groups. Since then the base and strong generating set have played a key role in the development of numerous group theoretic algorithms. The base and strong generating set also have applications to graph isomorphism testing, network theory, and backtrack search algorithms. A number of authors have noted that the size of the base has a direct effect on the space and time complexity of algorithms that use a base as a key ingredient. Given generators for a permutation group G on n letters, the question was posed as to whether or not a polynomial time greedy algorithm could be used to find a minimum base for G. We show that the greedy algorithm does not always find a minimum base for G. In fact, the minimum base problem is NP-hard, even if G is restricted to be a cyclic group or an abelian p-group. The corresponding decision problem, does there exist a base for G of size no more than K, is NP-complete. Let G be a permutation group of degree n, and suppose that G has a minimum base of size k. The maximum size of a nonredundant base for G is bounded above by O(k ~log~ n). Moreover, there exists an infinite family of permutation groups with: minimum base size k, degree n, and nonredundant base of size W (k ~log~ n). We have also obtained bounds for the size of a base produced by the greedy algorithm when G is restricted to be an abelian p-group. If G is an abelian p-group, then the size of a base produced by the greedy algorithm is bounded above by O(k ~log~ ~log~ n). Further, there exists an infinite family of abelian p-groups with: minimum base size k, degree n, and base produced by the greedy algorithm of size W (k ~log~ ~log~ n).
leff@smu.UUCP (Laurence Leff) (04/22/88)
TECHNICAL REPORTS FOR 1986 Computer and Information Science Department University of Oregon Eugene, OR 97403 CIS-TR-86-01 Parallel Computation and the NC Hierarchy Relativized by Christopher B. Wilson. Abstract: In this paper we construct oracles which allow us to compare complexity classes defined in terms of sequential resource measures to those defined in terms of parallel ones. It is known in the unrelativized case that NC sub 1 ~ !subset ~ L~ !subset ~NL~ !subset ~NC sub 2 ~ !subset ~ ... ~ !subset ~NC~ !subset ~P but none of these containments is known to be strict. First we introduce a natural model of relativized depth. It is shown that NC sub 1 subset L if and only if exist ~ A, NC sub 1 sup A subset L sup A, where subset denotes strict containment. We then exhibit oracles B and C with NC sub 1 sup B = NC sub 2 sup B = P sup B and NC sub 1 sup C ~ subset ~NC sub 2 sup C ~ subset ~ ... ~NC sup C ~ subset ~P sup C . Relativized depth is shown to be potentially powerful as there is a D such that for ~k, NC sub 1 sup D ~-~ NSPACE sup D (n sup k ) is nonempty. Finally, a new model of relativized space is proposed which is shown to retain most properties that hold in the unrelativized case. CIS-TR-86-02 Closed Environments: Partitioned Memory Representation for Parallel Logic Programs by John S. Conery. Abstract: An implementation technique for parallel logic programs is described. Variable bindings are stored in many small independent environments, with minimal sharing of information, unlike Prolog's three-stack representation which depends heavily on pointers from one activation record to another. The independent environments may be stored in different memories; a single global memory space is not required. Use of the new scheme is illustrated in the context of two parallel interpreters. CIS-TR-86-03 Parallel Algorithms for Permutation Groups and Graph Isomorphism by Eugene M. Luks. Abstract: We develop parallel techniques for dealing with permutation group problems. These are most effective on the class of groups with bounded non-albelian composition factors. For this class, we place in NC problems such as membership testing, finding the center and composition factors, and, of particular significance, finding pointwise-set-stabilizers. The last has applications to instances of graph-isomorphism and we show that NC contains isomorphism-testing for vertex-colored graphs with bounded color multiplicity, a problem not long known to be in polynomial time. CIS-TR-86-04 Artifacts at the Limit of Resolution by Kent A. Stevens and Daniel P. Lulich. Abstract: A visual illusion which appears at the limit of resolution is used to investigate perceived artifacts of the convolution by Gaussian filters. Evidence is provided that implicate the smallest size operator at the retina and that suggest that the perceived shape of intensity changes is influenced by artifacts induced by the operator. CIS-TR-86-05 Integrating Stereopsis with Monocular Interpretations of Planar Surfaces by Kent A. Stevens and Allen Brookes. Abstract: In a series of experiments in which stereo and monocular 3D interpretations were made mutually inconsistent, stereopsis was found to integrate with monocular depth only when disparities varied nonlinearly spatially. The apparent spatial disposition, including local surface orientation and depth ordering, was dominated by the monocular interpretation, even when stereo information provided strongly contradictory information. We conclude that stereo and monocular vision is integrated primarily on the basis of topographic features, not scalar depth values. Moreover, in interpreting depth from stereograms, we found a stereoscopic analogue to the familiar brightness contrast effect. The depth interpretation of stereo disparity information is roughly analogous to edge detection, with insensitivity to constant disparity gradients analogous to our insensitivity to linear (ramp-like) intensity distributions. This rules out several current models of spatial integration, and suggests new computational strategies. CIS-TR-86-06 Probing Depth in Monocular Images by Kent A. Stevens and Allen Brookes. Abstract: It is generally expected that depth (distance) is the internal representational primitive that corresponds to much of the perception of 3D. We tested this assumption in monocular surface stimuli that are devoid of distance information (due to orthographic projection and the chosen surface shape, with perspective projection used as a control) and yet are vividly three-dimensional. Slant judgments were found to be in close correspondence with the actual geometric slant of the stimuli; the spatial orientation of the surfaces was perceived accurately. The apparent depth in these stimuli was then tested by superimposing a stereo depth probe over the monocular surface. In both the perspective and orthographic project the gradient of perceived depth, measured by matching the apparent depth of the stereo probe with that of the monocular surface at a series of locations, was substantial. The experiments demonstrate that in orthographic projection the visual system can compute from local surface orientation a depth quantity that is commensurate with the relative depth derived from stereo disparity. The depth data suggests that, at least in the near field, the zero value for relative depth lies at the same absolute depth, as the stereo horopter (locus of zero stereo disparity). Relative to this zero value, the depth-from-slant computation seems to provide an estimate of distance information that is independent of the absolute distance to the surface. CIS-TR-86-07 Forbidden Minors Characteriziation of Partial 3-trees by Andrzej Proskurowski, Stefan Arnborg, and Derek Corneil. Abstract: A k-tree is formed from a k-complete graph by recursively adding a vertex adjacent to all vertices in an existing k-complete subgraph. The many applications of partial k-trees (subgraphs of k-trees) have motivated their study from both the algorithmic and theoretical points of view. In this paper we characterize the class of partial 3-trees by its set of four minimal forbidden minors (H is a minor of G if H can be obtained from G by a finite sequence of edge-extraction and edge-contraction operations). .bp CIS-TR-86-08 Automating the Analysis Process: An Example by Stephen Fickas. Abstract: Our goal is the automation of the requirements analysis process using a problem solving approach. In this paper we discuss a) the components of our ideal system, b) the test of a smaller demonstration system on problem #1 from the workshop problem set, and c) our prescription for further work in the area. CIS-TR-86-09 Backward Execution in Nondeterministic AND-Parallel Systems by John Conery. Abstract: A new algorithm for ``backward execution'' in AND-parallel logic programs is described, and new implementation techniques for this class of algorithm are introduced. The dataflow graph that determines forward and backward execution orders, the status of subgoals, and other state information in an AND process are represented by bitsets, and the steps of the algorithm are efficient operations on bitsets. Data from simulations show the implementation techniques are effective, and form the basis of several interesting future experiments. CIS-TR-86-10 Detecting Structure by Symbolic Constructions on Tokens by Kent A. Stevens and Allen Brookes. Abstract: Geometric organization is readily detected in discrete textures such as dot patterns. A common proposal is that orientation-tuned receptive field mechanisms provide the local orientation information from which the global organizations emerge. Alternatively, the local orientation might be attributed to grouping constructions between adjacent tokens, each representing the position of a dot and its attributes such as color, size and contrast. Geometric organization would then emerge by grouping operations on selected tokens that are similar, adjacent and aligned. It is the ability to group on the basis of similarity that most strongly differentiates this from the energy-summating receptive field approach. Using dot patterns with rivalrous organization, we demonstrate grouping phenomena that are difficult to attribute to a broad class of energy summation detectors operating in the spatial frequency domain, which we therefore attribute to perceptual groupings on tokens. We discuss the computational differences between feature detection and structure detection, and suggest that orientation-tuned receptive field mechanisms, while appropriate for the former task, have little application to the latter. CIS-TR-86-12 Synthesizing Systolic Arrays with Control Signals from Recurrence Equations by Sanjay V. Rajopadhye and Richard M. Fujimoto. Abstract: We present a technique for synthesizing systolic arrays which have non-uniform data flow governed by control signals. The starting point of the synthesis process is a Recurrence Equation with Linear Depencencies (RELD) which is a generalization of the simple recurrences encountered in mathematics. The process of synthesis consists of three stages. Since such a recurrence defines a dependency graph similar to a program dependency graph, the first stage involves the determination of a linear schedule (also called an affine timing function) and a linear allocation function for the RELD. The second stage consists of explicitly pipelining the dependencies so that the data flow is guaranteed to be localized. We present a unified theory for this pipelining process and show that it yields recurrences that have linear conditional expressions governing the computation. The third step naturally follows from this and consists of deriving control signals from the linear conditional expressions. The approach is illustrated by deriving the Guibas-Kung-Thompson architecture for optimum string parenthesization. CIS-TR-86-13 Heuristic Algorithms for Task Assignment in Distributed Computing Systems by Virginia M. Lo. Abstract: In this paper we investigate the problem of task assignment in distributed computing systems, i.e., given a set of k communicating tasks to be executed on a distributed system of n processors, to which processor should each task be assigned? We propose a family of heuristic algorithms for Stone's classic model of communicating tasks which considers the execution cost of each task on each processor and the communication costs between tasks. We augment this model to include interference costs which reflect the degree of incompatibility between two tasks. Whereas high communication costs serve as a force of attraction between tasks, causing them to be assigned to the same processor, interference costs serve as a force of repulsion between tasks, causing them to be distributed over many processors. The inclusion of interference costs in the model yields assignments with greater concurrency thus overcoming the tendency of Stone's model to assign all tasks to one or a few processors. Simulation results show that our algorithms perform well and in particular, that the highly efficient Simple Greedy Algorithm performs almost as well as more complex heuristic algorithms. When we consider task assignment to be an initial placement of tasks subject to subsequent refinement by dynamic task migration algorithms, efficient algorithms such as Simple Greedy are attractive candidates for practical distributed systems. If task assignment modules make a permanent assignment of tasks to processors, the increased overhead of a more complex heuristic is justified for the improvement in the assignment. CIS-TR-86-14 Intelligent Scheduling in Distributed Computing Systems by Virginia M. Lo and David Chen. Abstract: Our research into the problem of scheduling in distributed computing systems indicates that several techniques and tools from the area of ``expert systems'' can be successfully adapted for use in the design of a smart distributed scheduler. In this paper we look at expert system approaches to the representation of imprecise knowledge, techniques for reasoning about imprecise and unreliable knowledge, and means for handling knowledge accumulated over time. We show that that these are precisely the types of knowledge a distributed systems scheduler must deal with in order to make scheduling decisions and we give examples of the use of these techniques in the realm of task assignment and task migration algorithms. We then describe a task migration algorithm we have designed which utilizes rule based programming and expert systems techniques to deal with out-of-date and thus potentially unreliable data in system load tables. CIS-TR-86-16 Finding a Minimum Base for Permutation Groups is NP-hard by Kenneth D. Blaha. Abstract: The notions of a base and strong generating set were defined by Sims in 1970, and used as an efficient method to store and analyze large permutation groups. Since then the base and strong generating set have played a key role in the development of numerous group theoretic algorithms. The base and strong generating set also have applications to graph isomorphism testing, network theory, and backtrack search algorithms. A number of authors have noted that the size of the base has a direct effect on the space and time complexity of algorithms that use a base as a key ingredient. Given generators for a permutation group G on n letters, the question was posed as to whether or not a polynomial time greedy algorithm could be used to find a minimum base for G. We show that the greedy algorithm does not always find a minimum base for G. In fact, the minimum base problem is NP-hard, even if G is restricted to be a cyclic group or an abelian p-group. The corresponding decision problem, does there exist a base for G of size no more than K, is NP-complete. Let G be a permutation group of degree n, and suppose that G has a minimum base of size k. The maximum size of a nonredundant base for G is bounded above by O(k ~log~ n). Moreover, there exists an infinite family of permutation groups with: minimum base size k, degree n, and nonredundant base of size W (k ~log~ n). We have also obtained bounds for the size of a base produced by the greedy algorithm when G is restricted to be an abelian p-group. If G is an abelian p-group, then the size of a base produced by the greedy algorithm is bounded above by O(k ~log~ ~log~ n). Further, there exists an infinite family of abelian p-groups with: minimum base size k, degree n, and base produced by the greedy algorithm of size W (k ~log~ ~log~ n).