Technical reports

We introduce spatial graphs through a natural extension of the concept of planarity in three dimensions. For a graph G=(V,E), a face is a simple cycle of edges, and a complete set of faces is such that each edge belonging to a cycle in E is on at least one face in the set. G is spatial if admits a three-dimensional representation R with a complete set of faces consisting of simple surfaces, such that no two faces intersect except along the common edge. In particular G is called k-spatial if R includes k cells (spatial regions); and is called plane-face spatial if all the faces in R are plane. We prove that all graphs are 1-spatial, but not all of them are (k>1)-spatial or plane-face spatial. In particular, $K_n$ is $(n^2-3n)/2$-spatial and plane-face spatial. We derive some basic properties of spatial graphs as natural three-dimensional extensions of the properties of planar graphs.

Among practical methods for large-scale for Nondifferentiable Optimization (NDO), Bundle methods are widely recognized to play a relevant role; despite their potential, however, they are not often utilized for maximization of polyhedral functions, that appears in many different context such as Lagrangean Duals and decomposition algorithms, since simpler-to-program but less efficient approaches like subgradient methods are preferred. The aim of this work is to provide an applications-oriented survey of the theory of Bundle methods when applied to problems arising in continuous and combinatorial optimization, with an introduction to the several variants of Bundle approaches that can be built up by using a limited set of basic concepts and tools.

The past few years have seen a rise in popularity of massively parallel architectures that use fat-trees as their interconnection In this paper we formalize a parametric family of fat-trees, the k-ary n-trees, built with constant arity switches interconnected in a regular topology. A simple adaptive routing algorithm for k-ary n-trees sends each message to one of the nearest common ancestors (NCA) of both source and destination choosing the less loaded physical channels and then reaches the destination following the unique available path. Through simulation on a 4-ary 4-tree with 256 nodes, we analyze some variants of the adaptive algorithm that utilize wormhole routing with 1, 2 and 4 virtual channels. The experimental results show that the uniform, bit reversal and transpose traffic patterns are very sensitive to the flow control strategy. In all these cases, the saturation points are between 35-40% of the network capacity with 1 virtual channel, 55-60% with 2 virtual channels and around 75% with 4 virtual channels and after saturation, the network throughput remains stable. Increasing the number of virtual channels slightly worsens the average network latency, but improves the bounds on the distribution. The complement traffic, a representative of the class of the congestion-free communication patterns, reaches an optimal performance, with a saturation point at 97% of the capacity for all flow control strategies. In this case virtual channels are of little help and the average network latency experiences an increase proportional to the number of virtual channels, due to the multiplexing of several packets onto the same physical path.

We present a transformation from any conditional rewrite systems into non conditional ones and prove its correctness. The transformed systems are quite intuitive and well suited for parallel execution. We also show how termination and confluence of the original system are preserved in the transformed one.

We introduce rewriting with two sets of rules, the first interpreted equationally and the second not. A semantic view considers equational rules as defining an equational theory and reduction rules as defining a rewrite relation modulo this theory. An operational view considers both sets of rules as similar. We introduce sufficient properties for these two views to be equivalent (up to different notions of equivalence). The paper ends with a collection of example showing the effectiveness of this approach.

Bundle methods for Nondifferentiable Optimization are widely recognised as one of the best choices for the solution of Lagrangean Duals; one of their major drawbacks is that they require the solution of a Semidefinite Quadratic Programming subproblem at every iteration. We present an active-set method for the solution of such problems, that enhances upon the ones in the literature by distinguishing among bases with different properties and exploiting their structure in order to reduce the computational cost of the basic step. Furthermore, we show how the algorithm can be adapted to the several needs that arises in practice within Bundle algorithms; we describe how it is possible to allow constraints on the primal direction, how special (box) constraints can be more efficiently dealt with and how to accommodate changes in the number of variables of the nondifferentiable function. Finally, we describe the important implementation issues, and we report some computational experience to show that the algorithm is competitive with other QP codes when used within a Bundle code for the solution of Lagrangean Duals of large-scale (Integer) Linear Programs.

In this document, we discuss a prototype compiler of P3L, which is a structured parallel programming language, on a network of heterogeneous workstations. P3L is implemented on top of the abstract parallel machine provided by PVM. In particular, we discuss the definition of a new set of implementation templates, which are designed in order to meet the target features, and we show how the correct configurations for the abstract machine can be automatically generated within the support. (The document is written in Italian.)

We show how Labeling RAAM (LRAAM) can be exploited to generate `on the fly' neural networks for associative access of labeled structures. The topology of these networks, that we call Generalized Hopfield Networks (GHN), depends on the topology of the query used to retrieve information, and the weights on the networks' connections are the weights of the LRAAM encoding the structures. A method for incremental discovering of multiple solutions to a given query is presented. This method is based on terminal repellers, which are used to `delete' known solutions from the set of admissible solutions to a query. Terminal repellers are also used to implement exceptions at query level, i.e., when a solution to a query must satisfy some negative constraints on the labels and/or substructures. Besides, the proposed model solves very naturally the connectionist variable binding problem at query level. Some results for a tree-like query are presented. Finally, we define a parallel mode of execution, exploiting terminal repellers, for the GHN, and we propose to use terminal attractors for implementing shared variables and graph queries.

Parallelism, Optimal Data Distribution/Collection, P3L This document describes the MAP paradigm of parallelism and the problems related to its e cient imple- mentation on a 2D-mesh. In particular, we rst discuss how parallel algorithms ex- ploiting MAP parallelism can be easily expressed by using the P3L Map construct. Then, we discuss an implementation template for a massively parallel architecture with a 2D-mesh topology and Transputer-like processing nodes. The template is asymptotically optimal with respect to the strategies embedded for data distribu- tion, data collection and process allocation