Deadlock-Free
Fully-Adaptive Minimal Routing Algorithms: Limitations and Solutions
P.
López, J. Duato
Abstract.
In previous papers, a theory for the design of deadlock-free adaptive routing
algorithms as well as a design methodology have been proposed. In this paper, an
adaptive routing algorithm, obtained from the application of this theory to the
3-D torus, is evaluated under different load conditions and compared with other
algorithms. The results show that this algorithm is very fast, also increasing
the network throughput considerably.
Nevertheless, this adaptive algorithm has cycles in its channel
dependency graph. Consequently, when the network is heavily loaded messages may
temporarily block cyclically, drastically reducing the performance of the
algorithm. Two mechanisms are proposed to avoid this problem.
An
Event-Driven Net Based Simulation Methodology within a Knowledge-Based Framework
V.
Cingel, P. Friè
Abstract.
This paper presents a unified approach to the modelling and simulation of
parallel real-time systems using event-driven nets. A new paradigm of the
modelling and simulation based on the utilization of knowledge-based systems is
introduced. The simulation process is analyzed and the steps in simulation model
design and evaluation, where knowledge-based systems can be successfully used,
are indicated. The problem of required knowledge representation is also
elaborated. To highlight the facilities of the proposed approach, a model of a
small production cell is studied.
A
Framework for Cooperative Deductive Database Systems
M.K.
Mohania, N.L. Sarda
Abstract.
In this paper, we address the problems of design, management, and integration of
deductive database systems in a loosely coupled architecture, which constitute a
cooperative deductive database system. We next address one important aspect of
the problem of designing a cooperative deductive database system, namely,
allocation of rules across the deductive database systems. We identify
communication cost as the primary consideration in allocation of rules. The
problem of optimal allocation of rules has been shown NP-complete, which has
prohibitive execution times for large knowledge bases.
We propose a naïve algorithm for rule allocation and study its
performance experimentally. We also show that this naïve algorithm can be used
for reallocation of rules after rulebase gets updated.
A
Parallel Functional Language with First-Class Continuations. Programming Style
and Semantics
L.
Moreau
Abstract.
We present an operational semantics for a functional language with first-class
continuations and transparent constructs for parallelism fork and pcall. The
sequential semantics of programs with first-class continuations is preserved
when parallel evaluation is allowed, by verifying whether some
expressions have returned a value before applying a continuation. These
expressions are the ones that are evaluated before this continuation is applied
in a left-to-right sequential order. An implementation is proposed using a
notion of higher-order continuation that we call metacontinuation. This
semantics is costless when first-class continuations are not used. Several
programs also illustrate the programming style that can be adopted in such a
language.
The
Hardware Accelerator SFDL/SCL
J.
Blatný, D. Bartonìk
Abstract.
This paper presents a new multiprocessor architecture for modelling and
simulation of digital circuits. To speed up the simulation process a special
static algorithm for dividing modelled circuit components into equivalent
classes (before the simulation starts) has been designed. In components of one
class events will never appear at the same time. The number of equivalent
classes is practically greater than or at least equal to the number of
processors (n); therefore the classes are reduced into n groups. The main
criteria in this process are: minimum data transmissions among processors and
maximum usage of processors.
All
information (tables, programs) about elements of one group are stored in local
memories of the processor assigned for that group. As the distribution into
classes and groups is an NP-complete time consuming problem, 2 heuristic
algorithms have been created for its solution. The first one is based on
colouring of oriented graphs equivalent to modelled circuits, the other one uses
matrix calculus. The results of simulation experiments proved that the designed
multiprocessor architecture can speed up the simulation process by more than two
orders in comparison with the classical simulation method.