Hardware/Software Design of Dynamic Real-Time Schedulers for Embedded Multiprocessor Systems

The new generation of multicore processors opens new perspectives for the design of embedded systems. Multiprocessing, however, poses new challenges to the scheduling of real-time applications, in which the ever-increasing computational demands are constantly flanked by the need of meeting critical time constraints. Many research works have contributed to this field introducing new advanced scheduling algorithms. However, despite many of these works have solidly demonstrated their effectiveness, the actual support for multiprocessor real-time scheduling offered by current operating systems is still very limited. This dissertation deals with implementative aspects of real-time schedulers in modern embedded multiprocessor systems. The first contribution is represented by an open-source scheduling framework, which is capable of realizing complex multiprocessor scheduling policies, such as G-EDF, on conventional operating systems exploiting only their native scheduler from user-space. A set of experimental evaluations compare the proposed solution to other research projects that pursue the same goals by means of kernel modifications, highlighting comparable scheduling performances. The principles that underpin the operation of the framework, originally designed for symmetric multiprocessors, have been further extended first to asymmetric ones, which are subjected to major restrictions such as the lack of support for task migrations, and later to re-programmable hardware architectures (FPGAs). In the latter case, this work introduces a scheduling accelerator, which offloads most of the scheduling operations to the hardware and exhibits extremely low scheduling jitter. The realization of a portable scheduling framework presented many interesting software challenges. One of these has been represented by timekeeping. In this regard, a further contribution is represented by a novel data structure, called addressable binary heap (ABH). Such ABH, which is conceptually a pointer-based implementation of a binary heap, shows very interesting average and worst-case performances when addressing the problem of tick-less timekeeping of high-resolution timers.

Exact Algorithms for Different Classes of Vehicle Routing Problems

We deal with five problems arising in the field of logistics: the Asymmetric TSP (ATSP), the TSP with Time Windows (TSPTW), the VRP with Time Windows (VRPTW), the Multi-Trip VRP (MTVRP), and the Two-Echelon Capacitated VRP (2E-CVRP). The ATSP requires finding a lest-cost Hamiltonian tour in a digraph. We survey models and classical relaxations, and describe the most effective exact algorithms from the literature. A survey and analysis of the polynomial formulations is provided. The considered algorithms and formulations are experimentally compared on benchmark instances. The TSPTW requires finding, in a weighted digraph, a least-cost Hamiltonian tour visiting each vertex within a given time window. We propose a new exact method, based on new tour relaxations and dynamic programming. Computational results on benchmark instances show that the proposed algorithm outperforms the state-of-the-art exact methods. In the VRPTW, a fleet of identical capacitated vehicles located at a depot must be optimally routed to supply customers with known demands and time window constraints. Different column generation bounding procedures and an exact algorithm are developed. The new exact method closed four of the five open Solomon instances. The MTVRP is the problem of optimally routing capacitated vehicles located at a depot to supply customers without exceeding maximum driving time constraints. Two set-partitioning-like formulations of the problem are introduced. Lower bounds are derived and embedded into an exact solution method, that can solve benchmark instances with up to 120 customers. The 2E-CVRP requires designing the optimal routing plan to deliver goods from a depot to customers by using intermediate depots. The objective is to minimize the sum of routing and handling costs. A new mathematical formulation is introduced. Valid lower bounds and an exact method are derived. Computational results on benchmark instances show that the new exact algorithm outperforms the state-of-the-art exact methods.

Petrology and geochemistry of Lipari Island (Aeolian archipelago): constraints on magma genesis and evolution

A full set of geochemical and Sr, Nd and Pb isotope data both on bulk-rock and mineral samples is provided for volcanic rocks representative of the whole stratigraphic succession of Lipari Island in the Aeolian archipelago. These data, together with petrographic observations and melt/fluid inclusion investigations from the literature, give outlines on the petrogenesis and evolution of magmas through the magmatic and eruptive history of Lipari. This is the result of nine successive Eruptive Epochs developing between 271 ka and historical times, as derived from recentmost volcanological and stratigraphic studies, combined with available radiometric ages and correlation of tephra layers and marine terrace deposits. These Eruptive Epochs are characterized by distinctive vents partly overlapping in space and time, mostly under control of the main regional tectonic trends (NNW-SSE, N-S and minor E-W). A large variety of lava flows, scoriaceous deposits, lava domes, coulees and pyroclastics are emplaced, ranging in composition through time from calcalkaline (CA) and high-K (HKCA) basaltic andesites to rhyolites. CA and HKCA basaltic andesitic to dacitic magmas were erupted between 271 and 81 ka (Eruptive Epochs 1-6) from volcanic edifices located along the western coast of the island (and subordinately the eastern Monterosa) and the M.Chirica and M.S.Angelo stratocones. These mafic to intermediate magmas mainly evolved through AFC and RAFC processes, involving fractionation of mafic phases, assimilation of wall rocks and mixing with newly injected mafic magmas. Following a 40 ka-long period of volcanic quiescence, the rhyolitic magmas were lately erupted from eruptive vents located in the southern and north-eastern sectors of Lipari between 40 ka and historical times (Eruptive Epochs 7-9). They are suggested to derive from the previous mafic to intermediate melts through AFC processes. During the early phases of rhyolitic magmatism (Eruptive Epochs 7-8), enclaves-rich rocks and banded pumices, ranging in composition from HKCA dacites to low-SiO2 rhyolites were erupted, representing the products of magma mixing between fresh mafic magmas and the fractionated rhyolitic melts. The interaction of mantle-derived magmas with the crust represents an essential process during the whole magmatic hystory of Lipari, and is responsible for the wide range of observed geochemical and isotopic variations. The crustal contribution was particularly important during the intermediate phases of activity of Lipari when the cordierite-bearing lavas were erupted from the M. S.Angelo volcano (Eruptive Epoch 5, 105 ka). These lavas are interpreted as the result of mixing and subsequent hybridization of mantle-derived magmas, akin to the ones characterizing the older phases of activity of Lipari (Eruptive Epochs 1-4), and crustal anatectic melts derived from dehydration-melting reactions of metapelites in the lower crust. A comparison between the adjacent islands of Lipari and Vulcano outlines that their mafic to intermediate magmas seem to be genetically connected and derive from a similar mantle source affected by different degrees of partial melting (and variable extent of crustal assimilation) producing either the CA magmas of Lipari (higher degrees) or the HKCA to SHO magmas of Vulcano (lower degrees). On a regional scale, the most primitive rocks (SiO2<56%, MgO>3.5%) of Lipari, Vulcano, Salina and Filicudi are suggested to derive from a similar MORB-like source, variably metasomatized by aqueous fluids coming from the slab and subordinately by the additions of sediments.

Black Hole and Galaxy Growth over Cosmic Time: the Chandra COSMOS Legacy Survey

The study of supermassive black hole (SMBH) accretion during their phase of activity (hence becoming active galactic nuclei, AGN), and its relation to the host-galaxy growth, requires large datasets of AGN, including a significant fraction of obscured sources. X-ray data are strategic in AGN selection, because at X-ray energies the contamination from non-active galaxies is far less significant than in optical/infrared surveys, and the selection of obscured AGN, including also a fraction of heavily obscured AGN, is much more effective. In this thesis, I present the results of the Chandra COSMOS Legacy survey, a 4.6 Ms X-ray survey covering the equatorial COSMOS area. The COSMOS Legacy depth (flux limit f=2x10^(-16) erg/s/cm^(-2) in the 0.5-2 keV band) is significantly better than that of other X-ray surveys on similar area, and represents the path for surveys with future facilities, like Athena and X-ray Surveyor. The final Chandra COSMOS Legacy catalog contains 4016 point-like sources, 97% of which with redshift. 65% of the sources are optically obscured and potentially caught in the phase of main BH growth. We used the sample of 174 Chandra COSMOS Legacy at z>3 to place constraints on the BH formation scenario. We found a significant disagreement between our space density and the predictions of a physical model of AGN activation through major-merger. This suggests that in our luminosity range the BH triggering through secular accretion is likely preferred to a major-merger triggering scenario. Thanks to its large statistics, the Chandra COSMOS Legacy dataset, combined with the other multiwavelength COSMOS catalogs, will be used to answer questions related to a large number of astrophysical topics, with particular focus on the SMBH accretion in different luminosity and redshift regimes.