Efficient trigger-broadcasting in heterogeneous clusters

Broadcasts in parallel computing environments are often used to trigger “personal” computations at the processors (or, nodes) that comprise the system. (The qualifier “personal” means that the triggered computations may differ in type and complexity at each node.) We present an algorithm for trigger-broadcasting in a node-heterogeneous cluster of workstations, which comes predictably close to minimizing the time for completing both the broadcast and the computations it triggers. The algorithm orchestrates its broadcast taking account of: the speeds of the cluster's constituent workstations, the speed of the cluster's network, and the complexities of the computations that the broadcast triggers. The algorithm is within a constant factor of optimal when the speeds of the cluster's workstations and of its network are independent of the number of workstations. The algorithm is exactly optimal when the cluster is homogeneous—no matter how diverse the “personal” computations are.     

A unifying approach for a class of problems in the computational geometry of polygons

A generalized problem is defined in terms of functions on sets and illustrated in terms of the computational geometry of simple planar polygons. Although its apparent time complexity is O(n ²), the problem is shown to be solvable for several cases of interest (maximum and minimum distance, intersection detection and rerporting) in O(n logn), O(n) or O(logn) time, depending on the nature of a specialized “selection” function. (Some of the cases can also be solved by the Voronoi diagram method; but time complexity increases with that approach.) A new use of monotonicity and a new concept of “locality” in set mappings contribute significantly to the derivation of the results.     

Minimum number of tardy jobs in single machine scheduling with release dates—an improved algorithm

Scheduling of n-jobs on a single machine is studied here where each job i has a specified ready time, processing time and due date. It is assumed that early jobs have early due dates. An algorithm that minimizes the number of tardy jobs for this problem has been presented in Kise et al. [1]. We adopt the “blocks” concept to modify their algorithm to eliminate unnecessary computations. The improved algorithm developed here also employs a backward searching process for tardy jobs and uses a stopping rule for this search to further reduce the computational requirements.     

Relations between diagonalization,proof systems,and complexity gaps

In this paper we study diagonal processes over time bounded computations of one-tape Turing machines by diagonalizing only over those machines for which there exist formal proofs that they operate in the given time bound. This replaces the traditional “clock” in resource bounded diagonalization by formal proofs about running times and establishes close relations between properties of proof systems and existence of sharp time bounds for one-tape Turing machine complexity classes. These diagonalization methods also show that the Gap Theorem for resource bounded computations can hold only for those complexity classes which differ from the corresponding provable complexity classes. Furthermore, we show that there exist recursive time bounds T(n) such that the class of languages for which we can formally prove the existence of Turing machines which accept them in time T(n) differs from the class of languages accepted by Turing machines for which we can prove formally that they run in time T(n). We also investigate the corresponding problems for tape bound computations and discuss the difference time and tapebounded computations.     

The “book problem” and its neural correlates

Presence research can tell us why we feel present in the real world and can experience presence while using virtual reality technology (and movies and games) but has strikingly less to say on why we feel present in the scenes described in a book. Just how is it that the wonderful tangible detail of the real world or the complexity of digital technology can be matched and even surpassed by a story in a paperback book? This paper identifies a range of potential neurological solutions to this problem (and the “real world” and “dream” problems for good measure). We consider Jeannerod’s neural simulation of action, Grush’s emulation theory of representation and Rizzolatti’s work on mirror neurons as being candidate solutions to the “book problem”. We conclude by observing that these potential solutions further underline the “purpose” of presence is to act in the world whether it is real, virtual or solely in our imaginations.     

Elements of dynamic programming in local improvement constructions for heuristic solutions of routing problems with constraints

We consider methods for solving routing problems with precedence constraints that use iterative modes based on Bellman insertions while recomputing precedence constraints of the original problem; we assume that the dimension of the latter is sufficiently large, which does not let us, due to complexity of computations, immediately apply dynamic programming in the “global” version.     

Optimal configuration of an optical network providing predefined multicast transmissions

Operators of networks covering large areas are confronted with demands from some of their customers who are virtual service providers. These providers may call for the connectivity service which fulfills the specificity of their services, for instance a multicast transmission with allocated bandwidth. On the other hand, network operators want to make profit by trading the connectivity service of requested quality to their customers and to limit their infrastructure investments (or do not invest anything at all).We focus on circuit switching optical networks and work on repetitive multicast demands whose source and destinations are à priori known by an operator. He may therefore have corresponding trees “ready to be allocated” and adapt his network infrastructure according to these recurrent transmissions. This adjustment consists in setting available branching routers in the selected nodes of a predefined tree. The branching nodes are opto-electronic nodes which are able to duplicate data and retransmit it in several directions. These nodes are, however, more expensive and more energy consuming than transparent ones.In this paper we are interested in the choice of nodes of a multicast tree where the limited number of branching routers should be located in order to minimize the amount of required bandwidth. After formally stating the problem we solve it by proposing a polynomial algorithm whose optimality we prove. We perform exhaustive computations to show an operator gain obtained by using our algorithm. These computations are made for different methods of the multicast tree construction. We conclude by giving dimensioning guidelines and outline our further work.     

Computing spectral sequences

John McCleary insisted in his interesting textbook entitled “User’s guide to spectral sequences” on the fact that the tool “spectral sequence” is not in the general situation an algorithm allowing its user to compute the looked-for homology groups. The present article explains how the notion of “Object with Effective Homology” on the contrary allows the user to recursively obtain all the components of the Serre and Eilenberg–Moore spectral sequences, when the data are objects with effective homology. In particular the computability problem of the higher differentials is solved, the extension problem at abutment is also recursively solved. Furthermore, these methods have been concretely implemented as an extension of the Kenzo computer program. Two typical examples of spectral sequence computations are reported.     

Area-time lower-bound techniques with applications to sorting

Thearea-time complexity of VLSI computations is constrained by the flow and the storage of information in the two-dimensional chip. We study here the information exchanged across the boundary of the cells of asquare-tessellation of the layout. When the information exchange is due to thefunctional dependence between variables respectively input and output on opposite sides of a cell boundary, lower bounds are obtained on theAT ² measure (which subsume bisection bounds as a special case). When information exchange is due to thestorage saturation of the tessellation cells, a new type of lower bound is obtained on theAT measure. In the above arguments, information is essentially viewed as a fluid whose flow is uniquely constrained by the available bandwidth. However, in some computations, the flow is kept below capacity by the necessity to transform information before an output is produced. We call this mechanismcomputational friction and show that it implies lower bounds on theAT/logA measure. Regimes corresponding to each of the three mechanisms described above can appear by varying the problem parameters, as we shall illustrate by analyzing the problem of sortingn keys each ofk bits, for whichAT ²,AT, andAT/logA bounds are derived. Each bound is interesting, since it dominates the other two in a suitable range of key lengths and computations times.     

Local and global analysis of parametric solid sweeps

In this work, we propose a structured computational framework for modelling the envelope of the swept volume, that is the boundary of the volume obtained by sweeping an input solid along a trajectory of rigid motions. Our framework is adapted to the well-established industry-standard brep format to enable its implementation in modern CAD systems. This is achieved via a “local analysis”, which covers parametrizations and singularities, as well as a “global theory” which tackles face-boundaries, self-intersections and trim curves. Central to the local analysis is the “funnel” which serves as a natural parameter space for the basic surfaces constituting the sweep. The trimming problem is reduced to the problem of surface–surface intersections of these basic surfaces. Based on the complexity of these intersections, we introduce a novel classification of sweeps as decomposable and non-decomposable. Further, we construct an invariant function θ on the funnel which efficiently separates decomposable and non-decomposable sweeps. Through a geometric theorem we also show intimate connections between θ, local curvatures and the inverse trajectory used in earlier works as an approach towards trimming. In contrast to the inverse trajectory approach of testing points, θ is a computationally robust global function. It is the key to a complete structural understanding, and an efficient computation of both, the singular locus and the trim curves, which are central to a stable implementation. Several illustrative outputs of a pilot implementation are included.     

Top-k typicality queries and efficient query answering methods on large databases

Finding typical instances is an effective approach to understand and analyze large data sets. In this paper, we apply the idea of typicality analysis from psychology and cognitive science to database query answering, and study the novel problem of answering top-k typicality queries. We model typicality in large data sets systematically. Three types of top-k typicality queries are formulated. To answer questions like “Who are the top-k most typical NBA players?”, the measure of simple typicality is developed. To answer questions like “Who are the top-k most typical guards distinguishing guards from other players?”, the notion of discriminative typicality is proposed. Moreover, to answer questions like “Who are the best k typical guards in whole representing different types of guards?”, the notion of representative typicality is used. Computing the exact answer to a top-k typicality query requires quadratic time which is often too costly for online query answering on large databases. We develop a series of approximation methods for various situations: (1) the randomized tournament algorithm has linear complexity though it does not provide a theoretical guarantee on the quality of the answers; (2) the direct local typicality approximation using VP-trees provides an approximation quality guarantee; (3) a local typicality tree data structure can be exploited to index a large set of objects. Then, typicality queries can be answered efficiently with quality guarantees by a tournament method based on a Local Typicality Tree. An extensive performance study using two real data sets and a series of synthetic data sets clearly shows that top-k typicality queries are meaningful and our methods are practical.     

An efficient approach to finding potential products continuously

Skyline points and queries are important in the context of processing datasets with multiple dimensions. As skyline points can be viewed as representing marketable products that are useful for clients and business owners, one may also consider non-skyline points that are highly competitive with the current skyline points. We address the problem of continuously finding such potential products from a dynamic d-dimensional dataset, and formally define a potential product and its upgrade promotion cost. In this paper, we propose the CP-Sky algorithm, an efficient approach for continuously evaluating potential products by utilizing a second-order skyline set, which consists of candidate points that are closest to regular skyline points (also termed the first-order skyline set), to facilitate efficient computations and updates for potential products. With the knowledge of the second-order skyline set, CP-Sky enables the system to (1) efficiently find substitute skyline points from the second-order skyline set only if a first-order skyline point is removed, and (2) continuously retrieve the top-k potential products. Within this context, the Approximate Exclusive Dominance Region algorithm (AEDR) is proposed to reduce the computational complexity of determining a candidate set for second-order skyline updates over a dynamic data set without affecting the result accuracy. Additionally, we extend the CP-Sky algorithm to support the computations of top-k potential products. Finally, we present experimental results on data sets with various distributions to demonstrate the performance and utility of our approach.     

Termination Preserving Problem in the Transformation of Applicative Programs

Program transformation is a promising area of software methodology.TheFolding/Unfolding method proposed by Burstall/Darlington is a simple and powerfultransformation method for applicative programs.The only operations used are folding andunfolding of function definitions and substitution using laws.The major drawback of thismethod is that only partial correctness of functions is preserved and termination may be lost.That is if function f_1 is transformed to f_n,the computation of f_n on an object x will reach thesame result of the computation of f_1 on x,provided the computation terminates.But there maybe objects x,on which the computation of f_1 terminates,but f_n does not.This problem has notbeen solved with satisfaction.The idea of “reductive measure” of functions and “redactive”transformation is put forward here to solve the problem.It has been proved that if function's“complexity”is not increased under some reductive measure in the transformation process,termination will be preserved.The termination problem is thus solved to some extent.The mostimportant thing is that the simplicity of the original method is fully preserved.Because with thehelp of FP algebraic laws,the new restriction is expressed completely syntatically.Namely,onlythe direction of using laws(algebraic equations)for substitution is restricted.     

Alignment and Distribution Is Not (Always) NP-Hard

In this paper, an efficient algorithm to simultaneously implement array alignment and data/computation distribution is introduced and evaluated. We revisit previous work of J. Li and M. Chen (in “Frontiers 90: The Third Symposium on the Frontiers of Massively Parallel Computation,” pp. 424–433, College Park MD, Oct. 1990; and J. Parallel Distrib. Comput.13 (1991), 213–221), and we show that their alignment step should not be conducted without preserving the potential parallelism. In other words, the optimal alignment may well sequentialize computations, whatever the distribution afterward. We provide an efficient algorithm that handles alignment and data/computation distribution simultaneously. The good news is that several important instances of the whole alignment/distribution problem have polynomial complexity, while alignment itself is NP-complete (Li and Chen, 1990).     

Boundedness,hierarchy of fairness,and communication networks with delay

In this paper, we consider networks of communicating finite-state machines (CFSMs) with a delay-related fairness (T-fairness) constant imposed on all computations. The notion of T-fairness, in a sense, allows us to measure the degree of synchronization of parallel systems “quantitatively”. Based on the value of T, we define a hierarchy of unbounded networks. We are able to show that, in general, the hierarchy is infinite. However, if we restrict ourselves to networks of 2 machines, the hierarchy collapses all the way to the second level. We also derive the complexity result of the boundedness problem for CFSM networks with respect to T-fairness.     

A three-valued semantics for querying and repairing inconsistent databases

The problem of managing and querying inconsistent databases has been deeply investigated in the last few years. As the problem of consistent query answering is hard in the general case, most of the techniques proposed so far have an exponential complexity. Polynomial techniques have been proposed only for restricted forms of constraints (such as functional dependencies) and queries. In this paper, a technique for computing “approximate” consistent answers in polynomial time is proposed, which works in the presence of a wide class of constraints (namely, full constraints) and Datalog queries. The proposed approach is based on a repairing strategy where update operations assigning an undefined truth value to the “reliability” of tuples are allowed, along with updates inserting or deleting tuples. The result of a repair can be viewed as a three-valued database which satisfies the specified constraints. In this regard, a new semantics (namely, partial semantics) is introduced for constraint satisfaction in the context of three-valued databases, which aims at capturing the intuitive meaning of constraints under three-valued logic. It is shown that, in order to compute “approximate” consistent query answers, it suffices to evaluate queries by taking into account a unique repair (called deterministic repair), which in some sense “summarizes” all the possible repairs. The so obtained answers are “approximate” in the sense that are safe (true and false atoms in the answers are, respectively, true and false under the classical two-valued semantics), but not complete.     

An optimal time–space algorithm for dense stereo matching

The increasing demand for higher resolution images and higher frame rate videos will always pose a challenge to computational power when real-time performance is required to solve the stereo-matching problem in 3D reconstruction applications. Therefore, the use of asymptotic analysis is necessary to measure the time and space performance of stereo-matching algorithms regardless of the size of the input and of the computational power available. In this paper, we survey several classic stereo-matching algorithms with regard to time–space complexity. We also report running time experiments for several algorithms that are consistent with our complexity analysis. We present a new dense stereo-matching algorithm based on a greedy heuristic path computation in disparity space. A procedure which improves disparity maps in depth discontinuity regions is introduced. This procedure works as a post-processing step for any technique that solves the dense stereo-matching problem. We prove that our algorithm and post-processing procedure have optimal O(n) time–space complexity, where n is the size of a stereo image. Our algorithm performs only a constant number of computations per pixel since it avoids a brute force search over the disparity range. Hence, our algorithm is faster than “real-time” techniques while producing comparable results when evaluated with ground-truth benchmarks. The correctness of our algorithm is demonstrated with experiments in real and synthetic data.     

Goal and predictive coordination in two level hierarchical systems

The multilevel system theory applies two general methods of coordination, which influences the manner of subsystem management—goal and predictive coordinations. Both these general types of coordination perform multiple data transfer between the hierarchical levels and delay the evaluation and implementation of a global optimal solution of a control problem. The paper demonstrates a coordination policy, which decreases the information transfer in the hierarchical system, titled “noniterative” coordination. The last is developed both for goal and predictive coordination strategies. The mathematical foundations of these two noniterative coordination strategies are presented. Comparative analysis is performed to identify peculiarities and drawbacks for the real time management of two level hierarchical systems. Assessment of the computational workload and speed of the coordination, expressed as “flops” numbers is done for the case of nonlinear optimization problems. Both the noniterative coordination strategies benefit the real time operation in the multilevel system by reducing the iterative computations and the data transfer between the hierarchical levels. The predictive coordination has potential in speeding the management process and resource allocation, due to the decomposition approach, which is applied.     

Finding effective “force targets” for two-dimensional,multifinger frictional grips

In this paper we apply techniques from computational geometry to solve several problems in grasp planning and control in robotics. We consider the problem of calculating “force targets ” for a collection ofn fingers which grasp a two-dimensional object at known positions, at which the normals to the surface are also assumed to be known at least approximately. If the points at which the fingers touch the body do not allow apositive grip to be exerted (i.e., a grip in which the fingers hold the body in equilibrium by exerting friction-free forces in the directions of the corresponding inward-directed normals), it is appropriate to find the smallest coefficient of friction for which it is possible to assign a set of forces to be exerted by the fingers (so-calledfinger-force targets) which hold the object at equilibrium and such that each individual force lies within the corresponding cone of friction. We present an algorithm for this problem which runs in time0(n log² n log logn). We also present another algorithm for preprocessing the given data so as to allow fast computation of the desired coefficient of friction for the case in which one needs to balance any given “query” external force and torque. Finally, we discuss simpler variants of our techniques which are likely to be more efficient when the problem is solved for a small number of fingers.