Universal
Systems with Operations Related to Splicing
R.
Freund, F. Wachtler
Abstract.
Following some of the most recently obtained results on the computational
universality of specific variants of H systems (e.g. see [6, 9, 13] we introduce
systems based on new operations that are closely related to the splicing
operation, i.e. we consider the operations of cutting
a string at a specific site into two pieces with marking them at the cut ends
and of recombining two strings with
specifically marked endings. Whereas in the splicing of two strings these
strings are cut at specific sites and the cut pieces are recombined immediately
in a crosswise way, in the CR (cutting/recombination) systems introduced in this
paper cutting can happen independently from recombining the cut pieces.
Nevertheless, we shall show how a Turing machine computing a partial recursive
function can be simulated by an equivalent mCR system (i.e. a CR system working
in the multiset style, where the numbers of copies of all available strings are
counted) with a finite set of cutting/recombination rules as well as with a
finite set of axioms; in that way, from a universal Turing machine we obtain a
universal mCR system.
Dissemination
of Information in Vertex-Disjoint Paths Mode
J.
Hromkoviè, R. Klasing, E.A. Stöhr
Abstract.
The communication modes (one-way and two-way mode) used for disseminating
information among processors of interconnection networks via vertex-disjoint
paths in the communication step are investigated. The complexity of
communication algorithms is measured by the number of communication steps
(rounds). Since optimal broadcast and accumulation algorithms for these modes
can be achieved in a straightforward way for almost all interconnection networks
used, the paper concentrates on the gossip problem. The main results are listed
below:
1.
Optimal gossip algorithms for
paths, complete graphs and flakes in both modes.
2.
For hypercubes, cube-connected
cycles, butterfly networks, etc., gossip algorithms which are only about O
(log2log2n)
rounds slower than the optimal gossip algorithms on complete graphic are
designed.
Note
that the results achieved have also practical applications, because the
vertex/disjoint paths mode can be implemented in several hardware realisations
of computing networks.
PSEE:
A Tool for Parallel Systems Learning
E.
Luque, R. Suppi, J. Sorribes, E. Cesar, J. Falguera, M. Serrano
Abstract.
Programs for parallel computers of distributed memory are difficult to write,
understand, evaluate and debug. The design and performance evaluation of
algorithms is much more complex than the conventional sequential one. The
technical know/how necessary for the implementation of parallel systems is
already available, but a critical problem is in the handling of complexity. In
parallel distributed memory systems the performance is highly influenced by
factors as interconnection scheme, granularity, computing/communication ratio,
algorithm topology, parallel languages, and operating system policies.
Interaction between these factors is not easy to understand and often
unpredictable. This paper presents the PSEE (Parallel System Evaluation
Environment), an interactive graphical environment, which permits to study the
behaviour of parallel distributed memory systems, as well as several
enhancements to increase the goodness of this tool. PSEE is an easy-to-use
environment that enables parallel distributed memory systems programmers take
decisions about the behaviour program and parallel computer in terms such as
scalability, tuning and performance of the underlying parallel machine.
A
Cost Model for the Estimation Query Execution Time in a Parallel
Environment
Supporting Pipeline
M.
Spiliopoulou, M. Hatzopoulos, C. Vassilakis
Abstract.
We propose a model for the estimation of query execution time in an environment
supporting bushy and pipelined parallelism. We consider a parallel architecture
of processes having private main memories, accessing a shared secondary storage
and communicating to each other via a network. For this environment, we compute
the cost of query operators when processed in isolation and when in pipeline
mode. WE use those formulae to incrementally compute the cost of a query
execution plan from its components. Our cost model can be incorporated to any
optimizer for parallel query processing that considers parallel and pipelined
execution of the query operators.
Analysis
and Design of a Relational Database Management System and Implementation of its
Nucleus
M.C.
Fernández-Baizán, A. García, M.M. González, C. Pérez-Llera, R. Portaencasa,
E. Santos
Abstract.
This paper describes the objectives and characteristics of a new relational
database management system (RDBMS), that is being developed in the Technical
University of Madrid. The project includes a development of a user interface
based on the utilization of a universal relation, following the guidelines
presented by Ullman in [62]. For this we will implement a graphical interface of
similar characteristics to XWINDOWS. Furthermore, the RDBMS will be composed of
a nonprocedural query language, an integrated data dictionary which contains
database scheme in third normal form, a standard physical storage structure for
all databases, an access optimization system based on a new relational algebra (t
- algebra, defined by Garcia in [34] and published in [32]) and an integrity
constraint control system. On the other hand, this RDBMS will allow the
posterior development of a knowledge database system and an object-oriented
database system, considering results of researchers that are going to be carried
out in both areas.