A Unitary Approach to Information and Estimation Theory in Digital Communication Systems

This thesis presents the outcomes of a Ph.D. course in telecommunications engineering. It is focused on the optimization of the physical layer of digital communication systems and it provides innovations for both multi- and single-carrier systems. For the former type we have first addressed the problem of the capacity in presence of several nuisances. Moreover, we have extended the concept of Single Frequency Network to the satellite scenario, and then we have introduced a novel concept in subcarrier data mapping, resulting in a very low PAPR of the OFDM signal. For single carrier systems we have proposed a method to optimize constellation design in presence of a strong distortion, such as the non linear distortion provided by satellites' on board high power amplifier, then we developed a method to calculate the bit/symbol error rate related to a given constellation, achieving an improved accuracy with respect to the traditional Union Bound with no additional complexity. Finally we have designed a low complexity SNR estimator, which saves one-half of multiplication with respect to the ML estimator, and it has similar estimation accuracy.

An New Energetic Approach to the Modeling of Human Joint Kinematics: Application to the Ankle

The objective of this dissertation is to develop and test a predictive model for the passive kinematics of human joints based on the energy minimization principle. To pursue this goal, the tibio-talar joint is chosen as a reference joint, for the reduced number of bones involved and its simplicity, if compared with other sinovial joints such as the knee or the wrist. Starting from the knowledge of the articular surface shapes, the spatial trajectory of passive motion is obtained as the envelop of joint configurations that maximize the surfaces congruence. An increase in joint congruence corresponds to an improved capability of distributing an applied load, allowing the joint to attain a better strength with less material. Thus, joint congruence maximization is a simple geometric way to capture the idea of joint energy minimization. The results obtained are validated against in vitro measured trajectories. Preliminary comparison provide strong support for the predictions of the theoretical model.

Optical Microring Resonators based on ion-implanted LiNbO3 ridge waveguides

The growing interest for Integrated Optics for sensing, telecommunications and even electronics is driving research to find solutions to the new challenges issued by a more and more fast, connected and smart world. This thesis deals with the design, the fabrication and the characterisation of the first prototypes of Microring Resonators realised using ion implanted Lithium Niobate (LiNbO3) ridge waveguides. Optical Resonator is one among the most important devices for all tasks described above. LiNbO3 is the substrate commonly used to fabricate optical modulators thanks to its electro-optic characteristics. Since it is produced in high quantity, good quality and large wafers its price is low compared to other electro-optic substrate. We propose to use ion implantation as fabrication technology because in the other way standard optical waveguides realised in LiNbO3 by Proton Exchange (PE) or metal diffusion do not allow small bending radii, which are necessary to keep the circuit footprint small. We will show in fact that this approach allows to fabricate waveguides on Lithium Niobate that are better than PE or metal diffused waveguides as it allows smaller size devices and tailoring of the refractive index profile controlling the implantation parameters. Moreover, we will show that the ridge technology based on enhanced etching rate via ion implantation produces a waveguide with roughness lower than a dry etched one. Finally it has been assessed a complete technological process for fabrication of Microring Resonator devices in Lithium Niobate by ion implantation and the first prototypes have been produced.

Technical innovations for the diagnosis and the rehabilitation of motor and perceptive impairments of the child with Cerebral Palsy

The treatment of the Cerebral Palsy (CP) is considered as the “core problem” for the whole field of the pediatric rehabilitation. The reason why this pathology has such a primary role, can be ascribed to two main aspects. First of all CP is the form of disability most frequent in childhood (one new case per 500 birth alive, (1)), secondarily the functional recovery of the “spastic” child is, historically, the clinical field in which the majority of the therapeutic methods and techniques (physiotherapy, orthotic, pharmacologic, orthopedic-surgical, neurosurgical) were first applied and tested. The currently accepted definition of CP – Group of disorders of the development of movement and posture causing activity limitation (2) – is the result of a recent update by the World Health Organization to the language of the International Classification of Functioning Disability and Health, from the original proposal of Ingram – A persistent but not unchangeable disorder of posture and movement – dated 1955 (3). This definition considers CP as a permanent ailment, i.e. a “fixed” condition, that however can be modified both functionally and structurally by means of child spontaneous evolution and treatments carried out during childhood. The lesion that causes the palsy, happens in a structurally immature brain in the pre-, peri- or post-birth period (but only during the firsts months of life). The most frequent causes of CP are: prematurity, insufficient cerebral perfusion, arterial haemorrhage, venous infarction, hypoxia caused by various origin (for example from the ingestion of amniotic liquid), malnutrition, infection and maternal or fetal poisoning. In addition to these causes, traumas and malformations have to be included. The lesion, whether focused or spread over the nervous system, impairs the whole functioning of the Central Nervous System (CNS). As a consequence, they affect the construction of the adaptive functions (4), first of all posture control, locomotion and manipulation. The palsy itself does not vary over time, however it assumes an unavoidable “evolutionary” feature when during growth the child is requested to meet new and different needs through the construction of new and different functions. It is essential to consider that clinically CP is not only a direct expression of structural impairment, that is of etiology, pathogenesis and lesion timing, but it is mainly the manifestation of the path followed by the CNS to “re”-construct the adaptive functions “despite” the presence of the damage. “Palsy” is “the form of the function that is implemented by an individual whose CNS has been damaged in order to satisfy the demands coming from the environment” (4). Therefore it is only possible to establish general relations between lesion site, nature and size, and palsy and recovery processes. It is quite common to observe that children with very similar neuroimaging can have very different clinical manifestations of CP and, on the other hand, children with very similar motor behaviors can have completely different lesion histories. A very clear example of this is represented by hemiplegic forms, which show bilateral hemispheric lesions in a high percentage of cases. The first section of this thesis is aimed at guiding the interpretation of CP. First of all the issue of the detection of the palsy is treated from historical viewpoint. Consequently, an extended analysis of the current definition of CP, as internationally accepted, is provided. The definition is then outlined in terms of a space dimension and then of a time dimension, hence it is highlighted where this definition is unacceptably lacking. The last part of the first section further stresses the importance of shifting from the traditional concept of CP as a palsy of development (defect analysis) towards the notion of development of palsy, i.e., as the product of the relationship that the individual however tries to dynamically build with the surrounding environment (resource semeiotics) starting and growing from a different availability of resources, needs, dreams, rights and duties (4). In the scientific and clinic community no common classification system of CP has so far been universally accepted. Besides, no standard operative method or technique have been acknowledged to effectively assess the different disabilities and impairments exhibited by children with CP. CP is still “an artificial concept, comprising several causes and clinical syndromes that have been grouped together for a convenience of management” (5). The lack of standard and common protocols able to effectively diagnose the palsy, and as a consequence to establish specific treatments and prognosis, is mainly because of the difficulty to elevate this field to a level based on scientific evidence. A solution aimed at overcoming the current incomplete treatment of CP children is represented by the clinical systematic adoption of objective tools able to measure motor defects and movement impairments. A widespread application of reliable instruments and techniques able to objectively evaluate both the form of the palsy (diagnosis) and the efficacy of the treatments provided (prognosis), constitutes a valuable method able to validate care protocols, establish the efficacy of classification systems and assess the validity of definitions. Since the ‘80s, instruments specifically oriented to the analysis of the human movement have been advantageously designed and applied in the context of CP with the aim of measuring motor deficits and, especially, gait deviations. The gait analysis (GA) technique has been increasingly used over the years to assess, analyze, classify, and support the process of clinical decisions making, allowing for a complete investigation of gait with an increased temporal and spatial resolution. GA has provided a basis for improving the outcome of surgical and nonsurgical treatments and for introducing a new modus operandi in the identification of defects and functional adaptations to the musculoskeletal disorders. Historically, the first laboratories set up for gait analysis developed their own protocol (set of procedures for data collection and for data reduction) independently, according to performances of the technologies available at that time. In particular, the stereophotogrammetric systems mainly based on optoelectronic technology, soon became a gold-standard for motion analysis. They have been successfully applied especially for scientific purposes. Nowadays the optoelectronic systems have significantly improved their performances in term of spatial and temporal resolution, however many laboratories continue to use the protocols designed on the technology available in the ‘70s and now out-of-date. Furthermore, these protocols are not coherent both for the biomechanical models and for the adopted collection procedures. In spite of these differences, GA data are shared, exchanged and interpreted irrespectively to the adopted protocol without a full awareness to what extent these protocols are compatible and comparable with each other. Following the extraordinary advances in computer science and electronics, new systems for GA no longer based on optoelectronic technology, are now becoming available. They are the Inertial and Magnetic Measurement Systems (IMMSs), based on miniature MEMS (Microelectromechanical systems) inertial sensor technology. These systems are cost effective, wearable and fully portable motion analysis systems, these features gives IMMSs the potential to be used both outside specialized laboratories and to consecutive collect series of tens of gait cycles. The recognition and selection of the most representative gait cycle is then easier and more reliable especially in CP children, considering their relevant gait cycle variability. The second section of this thesis is focused on GA. In particular, it is firstly aimed at examining the differences among five most representative GA protocols in order to assess the state of the art with respect to the inter-protocol variability. The design of a new protocol is then proposed and presented with the aim of achieving gait analysis on CP children by means of IMMS. The protocol, named ‘Outwalk’, contains original and innovative solutions oriented at obtaining joint kinematic with calibration procedures extremely comfortable for the patients. The results of a first in-vivo validation of Outwalk on healthy subjects are then provided. In particular, this study was carried out by comparing Outwalk used in combination with an IMMS with respect to a reference protocol and an optoelectronic system. In order to set a more accurate and precise comparison of the systems and the protocols, ad hoc methods were designed and an original formulation of the statistical parameter coefficient of multiple correlation was developed and effectively applied. On the basis of the experimental design proposed for the validation on healthy subjects, a first assessment of Outwalk, together with an IMMS, was also carried out on CP children. The third section of this thesis is dedicated to the treatment of walking in CP children. Commonly prescribed treatments in addressing gait abnormalities in CP children include physical therapy, surgery (orthopedic and rhizotomy), and orthoses. The orthotic approach is conservative, being reversible, and widespread in many therapeutic regimes. Orthoses are used to improve the gait of children with CP, by preventing deformities, controlling joint position, and offering an effective lever for the ankle joint. Orthoses are prescribed for the additional aims of increasing walking speed, improving stability, preventing stumbling, and decreasing muscular fatigue. The ankle-foot orthosis (AFO), with a rigid ankle, are primarily designed to prevent equinus and other foot deformities with a positive effect also on more proximal joints. However, AFOs prevent the natural excursion of the tibio-tarsic joint during the second rocker, hence hampering the natural leaning progression of the whole body under the effect of the inertia (6). A new modular (submalleolar) astragalus-calcanear orthosis, named OMAC, has recently been proposed with the intention of substituting the prescription of AFOs in those CP children exhibiting a flat and valgus-pronated foot. The aim of this section is thus to present the mechanical and technical features of the OMAC by means of an accurate description of the device. In particular, the integral document of the deposited Italian patent, is provided. A preliminary validation of OMAC with respect to AFO is also reported as resulted from an experimental campaign on diplegic CP children, during a three month period, aimed at quantitatively assessing the benefit provided by the two orthoses on walking and at qualitatively evaluating the changes in the quality of life and motor abilities. As already stated, CP is universally considered as a persistent but not unchangeable disorder of posture and movement. Conversely to this definition, some clinicians (4) have recently pointed out that movement disorders may be primarily caused by the presence of perceptive disorders, where perception is not merely the acquisition of sensory information, but an active process aimed at guiding the execution of movements through the integration of sensory information properly representing the state of one’s body and of the environment. Children with perceptive impairments show an overall fear of moving and the onset of strongly unnatural walking schemes directly caused by the presence of perceptive system disorders. The fourth section of the thesis thus deals with accurately defining the perceptive impairment exhibited by diplegic CP children. A detailed description of the clinical signs revealing the presence of the perceptive impairment, and a classification scheme of the clinical aspects of perceptual disorders is provided. In the end, a functional reaching test is proposed as an instrumental test able to disclosure the perceptive impairment. References 1. Prevalence and characteristics of children with cerebral palsy in Europe. Dev Med Child Neurol. 2002 Set;44(9):633-640. 2. Bax M, Goldstein M, Rosenbaum P, Leviton A, Paneth N, Dan B, et al. Proposed definition and classification of cerebral palsy, April 2005. Dev Med Child Neurol. 2005 Ago;47(8):571-576. 3. Ingram TT. A study of cerebral palsy in the childhood population of Edinburgh. Arch. Dis. Child. 1955 Apr;30(150):85-98. 4. Ferrari A, Cioni G. The spastic forms of cerebral palsy : a guide to the assessment of adaptive functions. Milan: Springer; 2009. 5. Olney SJ, Wright MJ. Cerebral Palsy. Campbell S et al. Physical Therapy for Children. 2nd Ed. Philadelphia: Saunders. 2000;:533-570. 6. Desloovere K, Molenaers G, Van Gestel L, Huenaerts C, Van Campenhout A, Callewaert B, et al. How can push-off be preserved during use of an ankle foot orthosis in children with hemiplegia? A prospective controlled study. Gait Posture. 2006 Ott;24(2):142-151.

Il mercato del fumetto dal cartaceo al digitale

Con questo lavoro ci si propone di esaminare il panorama del fumetto nel mondo a partire dalle ricerche di mercato a disposizione e l’argomento è stato scelto perché poco trattato in letteratura. I risultati ottenuti hanno portato a galla grosse lacune, soprattutto per quanto riguarda il reperimento di informazioni nel mercato del fumetto in Italia, all’interno del quale si è notato un cambiamento delle preferenze dei consumatori relativo al supporto da utilizzare per la fruizione dei contenuti, con uno spostamento verso il digitale.

Simulative Investigation on the Electronic, Vibrational and Optical Properties of the Ge2Sb2Te5 Chalcogenide

Chalcogenides are chemical compounds with at least one of the following three chemical elements: Sulfur (S), Selenium (Sn), and Tellurium (Te). As opposed to other materials, chalcogenide atomic arrangement can quickly and reversibly inter-change between crystalline, amorphous and liquid phases. Therefore they are also called phase change materials. As a results, chalcogenide thermal, optical, structural, electronic, electrical properties change pronouncedly and significantly with the phase they are in, leading to a host of different applications in different areas. The noticeable optical reflectivity difference between crystalline and amorphous phases has allowed optical storage devices to be made. Their very high thermal conductivity and heat fusion provided remarkable benefits in the frame of thermal energy storage for heating and cooling in residential and commercial buildings. The outstanding resistivity difference between crystalline and amorphous phases led to a significant improvement of solid state storage devices from the power consumption to the re-writability to say nothing of the shrinkability. This work focuses on a better understanding from a simulative stand point of the electronic, vibrational and optical properties for the crystalline phases (hexagonal and faced-centered cubic). The electronic properties are calculated implementing the density functional theory combined with pseudo-potentials, plane waves and the local density approximation. The phonon properties are computed using the density functional perturbation theory. The phonon dispersion and spectrum are calculated using the density functional perturbation theory. As it relates to the optical constants, the real part dielectric function is calculated through the Drude-Lorentz expression. The imaginary part results from the real part through the Kramers-Kronig transformation. The refractive index, the extinctive and absorption coefficients are analytically calculated from the dielectric function. The transmission and reflection coefficients are calculated using the Fresnel equations. All calculated optical constants compare well the experimental ones.

Studio degli eventi erosivi in quattro aree campione della costa emiliano-romagnola

Il progetto di tesi ha analizzato i processi erosivi in atto in quattro aree della costa emilianoromagnola settentrionale, situate davanti a importanti foci fluviali: Volano, Reno, F. Uniti e Savio. Il lavoro di tesi si colloca all’interno di un progetto più ampio, che prevede la collaborazione tra la Regione Emilia Romagna, Servizio Geologico, Sismico e dei Suoli e l’Istituto di Scienze Marine ISMAR-CNR, sede di Bologna. Quest’ultimo ha acquisito, durante la campagna ERO2010, 210 km di profili sismici ad alta risoluzione in un’area sotto-costa, posta tra i 2 e gli 8 metri di profondità. Il lavoro di tesi ha usufruito di una nuova strategia di analisi, la sismica ad alta risoluzione (Chirp sonar), che ha permesso di identificare ed esaminare l’architettura geologica riconoscibile nei profili ed approfondire la conoscenza dell’assetto sub-superficiale dei depositi, ampliando le conoscenze di base riguardanti la dinamica dei litorali. L’interpretazione dei dati disponibili è avvenuta seguendo differenti fasi di studio: la prima, più conoscitiva, ha previsto l’identificazione delle evidenze di erosione nelle aree in esame mediante l’analisi della variazione delle linee di riva, l’osservazione delle opere poste a difesa del litorale e lo studio dell’evoluzione delle principali foci. Nella fase successiva le facies identificate nei profili sismici sono state interpretate in base alle loro caratteristiche geometriche ed acustiche, identificando le principali strutture presenti e interpretando, sulla base delle informazioni storiche apprese e delle conoscenze geologiche a disposizione, i corpi sedimentari riconosciuti. I nuovi profili Chirp sonar hanno consentito la ricostruzione geologica mediante la correlazione dei dati a mare (database ISMAR-CNR, Bologna, Carta geologica dei mari italiani 1:250.000) con quelli disponibili a terra, quali Carta dell’evoluzione storica dei cordoni costieri (Servizio Geologico e Sismico dei Suoli, Bo) e Carta geologica 1:50.000 (Servizio Geologico d’Italia e Progetto CARG). La conoscenza dei termini naturali e antropici dello stato fisico dei sistemi costieri è il presupposto necessario per l'esecuzione di studi ambientali atti a una corretta gestione integrata della costa. L’analisi approfondita della geologia superficiale fornisce un’opportunità per migliorare il processo decisionale nella gestione dei litorali e nella scelta degli interventi da attuare sulla costa, che devono essere fatti consapevolmente considerando l’assetto geologico e prevedendo una strategia di manutenzione della costa a medio termine. Un singolo intervento di ripascimento produce effetti di breve durata e non sufficienti a sanare il problema e a mitigare il rischio costiero. Nei tratti costieri scarsamente alimentati, soggetti a persistenti fenomeni erosivi, occorre, pertanto, mettere in atto ripetuti interventi di ripascimento accompagnati da un idoneo piano di monitoraggio.

In situ real-time investigation of Organic Ultra-Thin-Film transistors: growth, electrical properties and biosensing applications

Organic electronics has grown enormously during the last decades driven by the encouraging results and the potentiality of these materials for allowing innovative applications, such as flexible-large-area displays, low-cost printable circuits, plastic solar cells and lab-on-a-chip devices. Moreover, their possible field of applications reaches from medicine, biotechnology, process control and environmental monitoring to defense and security requirements. However, a large number of questions regarding the mechanism of device operation remain unanswered. Along the most significant is the charge carrier transport in organic semiconductors, which is not yet well understood. Other example is the correlation between the morphology and the electrical response. Even if it is recognized that growth mode plays a crucial role into the performance of devices, it has not been exhaustively investigated. The main goal of this thesis was the finding of a correlation between growth modes, electrical properties and morphology in organic thin-film transistors (OTFTs). In order to study the thickness dependence of electrical performance in organic ultra-thin-film transistors, we have designed and developed a home-built experimental setup for performing real-time electrical monitoring and post-growth in situ electrical characterization techniques. We have grown pentacene TFTs under high vacuum conditions, varying systematically the deposition rate at a fixed room temperature. The drain source current IDS and the gate source current IGS were monitored in real-time; while a complete post-growth in situ electrical characterization was carried out. At the end, an ex situ morphological investigation was performed by using the atomic force microscope (AFM). In this work, we present the correlation for pentacene TFTs between growth conditions, Debye length and morphology (through the correlation length parameter). We have demonstrated that there is a layered charge carriers distribution, which is strongly dependent of the growth mode (i.e. rate deposition for a fixed temperature), leading to a variation of the conduction channel from 2 to 7 monolayers (MLs). We conciliate earlier reported results that were apparently contradictory. Our results made evident the necessity of reconsidering the concept of Debye length in a layered low-dimensional device. Additionally, we introduce by the first time a breakthrough technique. This technique makes evident the percolation of the first MLs on pentacene TFTs by monitoring the IGS in real-time, correlating morphological phenomena with the device electrical response. The present thesis is organized in the following five chapters. Chapter 1 makes an introduction to the organic electronics, illustrating the operation principle of TFTs. Chapter 2 presents the organic growth from theoretical and experimental points of view. The second part of this chapter presents the electrical characterization of OTFTs and the typical performance of pentacene devices is shown. In addition, we introduce a correcting technique for the reconstruction of measurements hampered by leakage current. In chapter 3, we describe in details the design and operation of our innovative home-built experimental setup for performing real-time and in situ electrical measurements. Some preliminary results and the breakthrough technique for correlating morphological and electrical changes are presented. Chapter 4 meets the most important results obtained in real-time and in situ conditions, which correlate growth conditions, electrical properties and morphology of pentacene TFTs. In chapter 5 we describe applicative experiments where the electrical performance of pentacene TFTs has been investigated in ambient conditions, in contact to water or aqueous solutions and, finally, in the detection of DNA concentration as label-free sensor, within the biosensing framework.

Tecniche di ottimizzazione del software per sistemi su singolo chip per applicazioni di Nomadic Computing

I moderni sistemi embedded sono equipaggiati con risorse hardware che consentono l’esecuzione di applicazioni molto complesse come il decoding audio e video. La progettazione di simili sistemi deve soddisfare due esigenze opposte. Da un lato è necessario fornire un elevato potenziale computazionale, dall’altro bisogna rispettare dei vincoli stringenti riguardo il consumo di energia. Uno dei trend più diffusi per rispondere a queste esigenze opposte è quello di integrare su uno stesso chip un numero elevato di processori caratterizzati da un design semplificato e da bassi consumi. Tuttavia, per sfruttare effettivamente il potenziale computazionale offerto da una batteria di processoriè necessario rivisitare pesantemente le metodologie di sviluppo delle applicazioni. Con l’avvento dei sistemi multi-processore su singolo chip (MPSoC) il parallel programming si è diffuso largamente anche in ambito embedded. Tuttavia, i progressi nel campo della programmazione parallela non hanno mantenuto il passo con la capacità di integrare hardware parallelo su un singolo chip. Oltre all’introduzione di multipli processori, la necessità di ridurre i consumi degli MPSoC comporta altre soluzioni architetturali che hanno l’effetto diretto di complicare lo sviluppo delle applicazioni. Il design del sottosistema di memoria, in particolare, è un problema critico. Integrare sul chip dei banchi di memoria consente dei tempi d’accesso molto brevi e dei consumi molto contenuti. Sfortunatamente, la quantità di memoria on-chip che può essere integrata in un MPSoC è molto limitata. Per questo motivo è necessario aggiungere dei banchi di memoria off-chip, che hanno una capacità molto maggiore, come maggiori sono i consumi e i tempi d’accesso. La maggior parte degli MPSoC attualmente in commercio destina una parte del budget di area all’implementazione di memorie cache e/o scratchpad. Le scratchpad (SPM) sono spesso preferite alle cache nei sistemi MPSoC embedded, per motivi di maggiore predicibilità, minore occupazione d’area e – soprattutto – minori consumi. Per contro, mentre l’uso delle cache è completamente trasparente al programmatore, le SPM devono essere esplicitamente gestite dall’applicazione. Esporre l’organizzazione della gerarchia di memoria ll’applicazione consente di sfruttarne in maniera efficiente i vantaggi (ridotti tempi d’accesso e consumi). Per contro, per ottenere questi benefici è necessario scrivere le applicazioni in maniera tale che i dati vengano partizionati e allocati sulle varie memorie in maniera opportuna. L’onere di questo compito complesso ricade ovviamente sul programmatore. Questo scenario descrive bene l’esigenza di modelli di programmazione e strumenti di supporto che semplifichino lo sviluppo di applicazioni parallele. In questa tesi viene presentato un framework per lo sviluppo di software per MPSoC embedded basato su OpenMP. OpenMP è uno standard di fatto per la programmazione di multiprocessori con memoria shared, caratterizzato da un semplice approccio alla parallelizzazione tramite annotazioni (direttive per il compilatore). La sua interfaccia di programmazione consente di esprimere in maniera naturale e molto efficiente il parallelismo a livello di loop, molto diffuso tra le applicazioni embedded di tipo signal processing e multimedia. OpenMP costituisce un ottimo punto di partenza per la definizione di un modello di programmazione per MPSoC, soprattutto per la sua semplicità d’uso. D’altra parte, per sfruttare in maniera efficiente il potenziale computazionale di un MPSoC è necessario rivisitare profondamente l’implementazione del supporto OpenMP sia nel compilatore che nell’ambiente di supporto a runtime. Tutti i costrutti per gestire il parallelismo, la suddivisione del lavoro e la sincronizzazione inter-processore comportano un costo in termini di overhead che deve essere minimizzato per non comprometterre i vantaggi della parallelizzazione. Questo può essere ottenuto soltanto tramite una accurata analisi delle caratteristiche hardware e l’individuazione dei potenziali colli di bottiglia nell’architettura. Una implementazione del task management, della sincronizzazione a barriera e della condivisione dei dati che sfrutti efficientemente le risorse hardware consente di ottenere elevate performance e scalabilità. La condivisione dei dati, nel modello OpenMP, merita particolare attenzione. In un modello a memoria condivisa le strutture dati (array, matrici) accedute dal programma sono fisicamente allocate su una unica risorsa di memoria raggiungibile da tutti i processori. Al crescere del numero di processori in un sistema, l’accesso concorrente ad una singola risorsa di memoria costituisce un evidente collo di bottiglia. Per alleviare la pressione sulle memorie e sul sistema di connessione vengono da noi studiate e proposte delle tecniche di partizionamento delle strutture dati. Queste tecniche richiedono che una singola entità di tipo array venga trattata nel programma come l’insieme di tanti sotto-array, ciascuno dei quali può essere fisicamente allocato su una risorsa di memoria differente. Dal punto di vista del programma, indirizzare un array partizionato richiede che ad ogni accesso vengano eseguite delle istruzioni per ri-calcolare l’indirizzo fisico di destinazione. Questo è chiaramente un compito lungo, complesso e soggetto ad errori. Per questo motivo, le nostre tecniche di partizionamento sono state integrate nella l’interfaccia di programmazione di OpenMP, che è stata significativamente estesa. Specificamente, delle nuove direttive e clausole consentono al programmatore di annotare i dati di tipo array che si vuole partizionare e allocare in maniera distribuita sulla gerarchia di memoria. Sono stati inoltre sviluppati degli strumenti di supporto che consentono di raccogliere informazioni di profiling sul pattern di accesso agli array. Queste informazioni vengono sfruttate dal nostro compilatore per allocare le partizioni sulle varie risorse di memoria rispettando una relazione di affinità tra il task e i dati. Più precisamente, i passi di allocazione nel nostro compilatore assegnano una determinata partizione alla memoria scratchpad locale al processore che ospita il task che effettua il numero maggiore di accessi alla stessa.

Hybrid Methods for Resource Allocation and Scheduling Problems in Deterministic and Stochastic Environments

This work presents exact, hybrid algorithms for mixed resource Allocation and Scheduling problems; in general terms, those consist into assigning over time finite capacity resources to a set of precedence connected activities. The proposed methods have broad applicability, but are mainly motivated by applications in the field of Embedded System Design. In particular, high-performance embedded computing recently witnessed the shift from single CPU platforms with application-specific accelerators to programmable Multi Processor Systems-on-Chip (MPSoCs). Those allow higher flexibility, real time performance and low energy consumption, but the programmer must be able to effectively exploit the platform parallelism. This raises interest in the development of algorithmic techniques to be embedded in CAD tools; in particular, given a specific application and platform, the objective if to perform optimal allocation of hardware resources and to compute an execution schedule. On this regard, since embedded systems tend to run the same set of applications for their entire lifetime, off-line, exact optimization approaches are particularly appealing. Quite surprisingly, the use of exact algorithms has not been well investigated so far; this is in part motivated by the complexity of integrated allocation and scheduling, setting tough challenges for ``pure'' combinatorial methods. The use of hybrid CP/OR approaches presents the opportunity to exploit mutual advantages of different methods, while compensating for their weaknesses. In this work, we consider in first instance an Allocation and Scheduling problem over the Cell BE processor by Sony, IBM and Toshiba; we propose three different solution methods, leveraging decomposition, cut generation and heuristic guided search. Next, we face Allocation and Scheduling of so-called Conditional Task Graphs, explicitly accounting for branches with outcome not known at design time; we extend the CP scheduling framework to effectively deal with the introduced stochastic elements. Finally, we address Allocation and Scheduling with uncertain, bounded execution times, via conflict based tree search; we introduce a simple and flexible time model to take into account duration variability and provide an efficient conflict detection method. The proposed approaches achieve good results on practical size problem, thus demonstrating the use of exact approaches for system design is feasible. Furthermore, the developed techniques bring significant contributions to combinatorial optimization methods.

Architetture di interconnessione per sistemi su singolo chip e per sistemi ad integrazione tridimensionale

I continui sviluppi nel campo della fabbricazione dei circuiti integrati hanno comportato frequenti travolgimenti nel design, nell’implementazione e nella scalabilità dei device elettronici, così come nel modo di utilizzarli. Anche se la legge di Moore ha anticipato e caratterizzato questo trend nelle ultime decadi, essa stessa si trova a fronteggiare attualmente enormi limitazioni, superabili solo attraverso un diverso approccio nella produzione di chip, consistente in pratica nella sovrapposizione verticale di diversi strati collegati elettricamente attraverso speciali vias. Sul singolo strato, le network on chip sono state suggerite per ovviare le profonde limitazioni dovute allo scaling di strutture di comunicazione condivise. Questa tesi si colloca principalmente nel contesto delle nascenti piattaforme multicore ad alte prestazioni basate sulle 3D NoC, in cui la network on chip viene estesa nelle 3 direzioni. L’obiettivo di questo lavoro è quello di fornire una serie di strumenti e tecniche per poter costruire e aratterizzare una piattaforma tridimensionale, cosi come dimostrato nella realizzazione del testchip 3D NOC fabbricato presso la fonderia IMEC. Il primo contributo è costituito sia una accurata caratterizzazione delle interconnessioni verticali (TSVs) (ovvero delle speciali vias che attraversano l’intero substrato del die), sia dalla caratterizzazione dei router 3D (in cui una o più porte sono estese nella direzione verticale) ed infine dal setup di un design flow 3D utilizzando interamente CAD 2D. Questo primo step ci ha permesso di effettuare delle analisi dettagliate sia sul costo sia sulle varie implicazioni. Il secondo contributo è costituito dallo sviluppo di alcuni blocchi funzionali necessari per garantire il corretto funziomento della 3D NoC, in presenza sia di guasti nelle TSVs (fault tolerant links) che di deriva termica nei vari clock tree dei vari die (alberi di clock indipendenti). Questo secondo contributo è costituito dallo sviluppo delle seguenti soluzioni circuitali: 3D fault tolerant link, Look Up Table riconfigurabili e un sicnronizzatore mesocrono. Il primo è costituito fondamentalmente un bus verticale equipaggiato con delle TSV di riserva da utilizzare per rimpiazzare le vias guaste, più la logica di controllo per effettuare il test e la riconfigurazione. Il secondo è rappresentato da una Look Up Table riconfigurabile, ad alte prestazioni e dal costo contenuto, necesaria per bilanciare sia il traffico nella NoC che per bypassare link non riparabili. Infine la terza soluzione circuitale è rappresentata da un sincronizzatore mesocrono necessario per garantire la sincronizzazione nel trasferimento dati da un layer and un altro nelle 3D Noc. Il terzo contributo di questa tesi è dato dalla realizzazione di un interfaccia multicore per memorie 3D (stacked 3D DRAM) ad alte prestazioni, e dall’esplorazione architetturale dei benefici e del costo di questo nuovo sistema in cui il la memoria principale non è piu il collo di bottiglia dell’intero sistema. Il quarto ed ultimo contributo è rappresentato dalla realizzazione di un 3D NoC test chip presso la fonderia IMEC, e di un circuito full custom per la caratterizzazione della variability dei parametri RC delle interconnessioni verticali.