Constructs and evaluation strategies for intelligent speculative parallelism - armageddon revisited

This report addresses speculative parallelism (the assignment of spare processing resources to tasks which are not known to be strictly required for the successful completion of a computation) at the user and application level. At this level, the execution of a program is seen as a (dynamic) tree —a graph, in general. A solution for a problem is a traversal of this graph from the initial state to a node known to be the answer. Speculative parallelism then represents the assignment of resources to múltiple branches of this graph even if they are not positively known to be on the path to a solution. In highly non-deterministic programs the branching factor can be very high and a naive assignment will very soon use up all the resources. This report presents work assignment strategies other than the usual depth-first and breadth-first. Instead, best-first strategies are used. Since their definition is application-dependent, the application language contains primitives that allow the user (or application programmer) to a) indícate when intelligent OR-parallelism should be used; b) provide the functions that define "best," and c) indícate when to use them. An abstract architecture enables those primitives to perform the search in a "speculative" way, using several processors, synchronizing them, killing the siblings of the path leading to the answer, etc. The user is freed from worrying about these interactions. Several search strategies are proposed and their implementation issues are addressed. "Armageddon," a global pruning method, is introduced, together with both a software and a hardware implementation for it. The concepts exposed are applicable to áreas of Artificial Intelligence such as extensive expert systems, planning, game playing, and in general to large search problems. The proposed strategies, although showing promise, have not been evaluated by simulation or experimentation.

New data on the Pleistocene of Trani (Adriatic Coast, Southern Italy)

Along the Apulian Adriatic coast, in a cliff south of Trani, a succession of three units (superimposed on one another) of marine and/or paralic environments has been recognised. The lowest unit I is characterised by calcareous/siliciclastic sands (css), micritic limestones (ml), stromatolitic and characean boundstones (scb), characean calcarenites (cc). The sedimentary environment merges from shallow marine, with low energy and temporary episodes of subaerial exposure, to lagoonal with a few exchanges with the sea. The lagoonal stromatolites (scb subunit) grew during a long period of relative stability of a high sea level in tropical climate. The unit I is truncated at the top by an erosion surface on which the unit II overlies; this consists of a basal pebble lag (bpl), silicicla - stic sands (ss), calcareous sands (cs), characean boundstones (cb), brown paleosol (bp). The sedimentary environment varies from beach to lagoon with salinity variations. Although there are indications of seismic events within the subunits cs, unit II deposition took place in a context of relative stability. The unit II is referable to a sea level highstand. Unit III, trangressive on the preceding, consists of white calcareous sands (wcs), calcareous sands and calcarenites (csc), phytoclastic calcirudite and phytohermal travertine (pcpt), mixed deposits (csl, m, k, c), sands (s) and red/brown paleosols (rbp). The sedimentation of this unit was affected by synsedimentary tectonic, attested by seismites found at several heights. Also the unit III is referable to a sea level highstand. The scientific literature has so far generally attributed to the Tyrrhenian (auct.) the deposits of Trani cliff. As part of this work some datings were performed on 10 samples, using the amino acid racemization method (AAR) applied to ostracod carapaces. Four of these samples have been rejected because they have shown in laboratory recent contamination. The numerical ages indicate that the deposits of the Trani cliff are older than MIS 5. The upper part of the unit I has been dated to 355±85 ka BP, thus allowing to assign the lowest stromatolitic subunit (scb) at the MIS 11 peak and the top of the unit I at the MIS 11-MIS 10 interval. The base of the unit II has been dated to 333±118 ka BP, thus attributing the erosion surface that bounds the units I and II to the MIS 10 lowstand and the lower part of the unit II to MIS 9.3. The upper part of the unit II has been dated to 234±35 ka BP, while three other numerical ages come from unit III: 303±35, 267±51, 247±61 ka BP. At present, the numerical ages cannot distinguish the sedimentation ages of units II and III, which are both related to the MIS 9.3- MIS 7.1 time range. However, the position of the units, superimposed one another, and their respective age, allows us to recognise a subsidence phase between MIS 11 and MIS 7, followed by an uplift phase between the MIS 7 and the present day, which led the deposits in their current position. This tectonic pattern is not in full agreement with what is described in the literature for the Apulian foreland.

A combined algorithm for analyzing structural controllability and observability of complex networks

In this paper a combined algorithm for analyzing structural controllability and observability of complex networks is presented. The algorithm addresses the two fundamental properties to guarantee structural controllability of a system: the absence of dilations and the accessibility of all nodes. The first problem is reformulated as a Maximum Matching search and it is addressed via the Hopcroft- Karp algorithm; the second problem is solved via a new wiring algorithm. Both algorithms can be combined to efficiently determine the number of required controllers and observers as well as the new required connections in order to guarantee controllability and observability in real complex networks. An application to a Twitter social network with over 100,000 nodes illustrates the proposed algorithms.