Volume 19, 2000, No. 3

Efficient Total-Exchange in Wormhole-Routed Toroidal Cubes

F. Petrini

Abstract. The total-exchange is one of the most dense communication  patterns and is at the heart of numerous applications and programming models in parallel computing. In this paper we present a simple randomized algorithm to efficiently schedule the total exchange on a toroidal mesh with wormhole switching. This algorithm is based on an important property of the wormhole networks that reach high performance  under uniform traffic using adaptive routing. The experimental results, conducted on a 256 nodes bi-dimensional torus, show that this algorithm reaches a very high level of performance, around 90% of the optimal bound, and is more efficient than other algorithms presented in the literature.

A universal fixpoint semantics for ordered logic

E. Laenens, D. Vermeir

Ordered logic is the theoretical foundation of the LOCO programing language [9] which combines the declarative elegance and power of logic programming with asvantages of object-oriented systems. Ordered logic is based on a partially ordered structure of logical theories or objects. Objects are entities that may contain positive as well as negative information represented by rules. The partial order allows for the definition of a preference structure on these objects and consequently also on the information they contain.  The result is a simple yet powerful logic that models classical as well as non-monotonic inference mechanisms. The central issue of this paper is the definition of a universal fixpoint semantics for ordered logic programs which constitutes an important extension and generalization of the fixpoint semantics prresented in [11, in the sense that it computes all partial models (well-founded and stable partial models included) instead of only ´total´ models (a possibly empty subset of the stable partial models), thus overcoming the limitations of the previous approach.

ON DISCONTINUOUS OPTICAL FLOW

S. S. Beauchemin, J. L. Barron

Abstract. Retinal image motion and optical flow as its approximation are  fundamental concepts in the field of vision, perceptual and computational. However, the  computation of optical flow remains a challenging problem as image motion  includes discontinuities and multiple values mostly due to scene geometry, surface  translucency and various photometric effects such as surface reflectance. In this  contribution, we analyze image motion in the frequency space with respect to motion  iscontinuities and surface translucence. We derive, under models of constant and  linear optical flow, the frequency structure of motion discontinuities due to occlusion and we demonstrate its various geometrical properties. The aperture  problem is investigated and we show that the information content of an  occlusion almost always disambiguates the velocity of an occluding signal suffering from the aperture problem.

REAL TIME SPEED OF A CONSERVATIVE PARALLEL SIMULATION

N. Kalantery

Abstract. This paper examines the real time speed of the conservative  parallel simulation of a telecommunications network. Real time speed is defined as the ratio of the simulated time to the execution time. A generic simulation model of SS7 networks is executed under the conservative mechanism. A technique used to secure a stable lower bound on the  speed of the SS7 simulator is introduced and analyzed. Using this technique  simulation models ranging in size, from 16 to 64 nodes, are executed on similarly sized and  configured transputer networks. Empirical data on the real time performance of the system are presented. The results confirm that under the given conditions, the performance boundaries of the simulator are both stable and scalable: independent of work load density and size of the modeled network, simulation of a given period of model activity can be guaranteed within a predetermined period of real time.

Go To Contents