Progettazione e analisi di soluzioni per la QOS e il controllo di flusso in Networks-on-chip

Nel documento vengono principalmente trattati i principali meccanismi per il controllo di flusso per le NoC. Vengono trattati vari schemi di switching, gli stessi schemi associati all'introduzione dei Virtual Channel, alcuni low-level flow control, e due soluzioni per gli end-to-end flow control: Credit Based e CTC (STMicroelectronics). Nel corso della trattazione vengono presentate alcune possibili modifiche a CTC per incrementarne le prestazioni mantenendo la scalabilità che lo contraddistingue: queste sono le "back-to-back request" e "multiple incoming connections". Infine vengono introdotti alcune soluzioni per l'implementazione della qualità di servizio per le reti su chip. Proprio per il supporto al QoS viene introdotto CTTC: una versione di CTC con il supporto alla Time Division Multiplexing su rete Spidergon.

Implementazione dell'algoritmo filtered back-projection (FBP) per architetture low-power di tipo systems-on-chip

Il presente lavoro di tesi, svolto presso i laboratori dell'X-ray Imaging Group del Dipartimento di Fisica e Astronomia dell'Università di Bologna e all'interno del progetto della V Commissione Scientifica Nazionale dell'INFN, COSA (Computing on SoC Architectures), ha come obiettivo il porting e l’analisi di un codice di ricostruzione tomografica su architetture GPU installate su System-On-Chip low-power, al fine di sviluppare un metodo portatile, economico e relativamente veloce. Dall'analisi computazionale sono state sviluppate tre diverse versioni del porting in CUDA C: nella prima ci si è limitati a trasporre la parte più onerosa del calcolo sulla scheda grafica, nella seconda si sfrutta la velocità del calcolo matriciale propria del coprocessore (facendo coincidere ogni pixel con una singola unità di calcolo parallelo), mentre la terza è un miglioramento della precedente versione ottimizzata ulteriormente. La terza versione è quella definitiva scelta perché è la più performante sia dal punto di vista del tempo di ricostruzione della singola slice sia a livello di risparmio energetico. Il porting sviluppato è stato confrontato con altre due parallelizzazioni in OpenMP ed MPI. Si è studiato quindi, sia su cluster HPC, sia su cluster SoC low-power (utilizzando in particolare la scheda quad-core Tegra K1), l’efficienza di ogni paradigma in funzione della velocità di calcolo e dell’energia impiegata. La soluzione da noi proposta prevede la combinazione del porting in OpenMP e di quello in CUDA C. Tre core CPU vengono riservati per l'esecuzione del codice in OpenMP, il quarto per gestire la GPU usando il porting in CUDA C. Questa doppia parallelizzazione ha la massima efficienza in funzione della potenza e dell’energia, mentre il cluster HPC ha la massima efficienza in velocità di calcolo. Il metodo proposto quindi permetterebbe di sfruttare quasi completamente le potenzialità della CPU e GPU con un costo molto contenuto. Una possibile ottimizzazione futura potrebbe prevedere la ricostruzione di due slice contemporaneamente sulla GPU, raddoppiando circa la velocità totale e sfruttando al meglio l’hardware. Questo studio ha dato risultati molto soddisfacenti, infatti, è possibile con solo tre schede TK1 eguagliare e forse a superare, in seguito, la potenza di calcolo di un server tradizionale con il vantaggio aggiunto di avere un sistema portatile, a basso consumo e costo. Questa ricerca si va a porre nell’ambito del computing come uno tra i primi studi effettivi su architetture SoC low-power e sul loro impiego in ambito scientifico, con risultati molto promettenti.

OpenMP task scheduling strategies to mitigate hardware variability in tightly-coupled shared memory clusters

In questa tesi sono stati apportati due importanti contributi nel campo degli acceleratori embedded many-core. Abbiamo implementato un runtime OpenMP ottimizzato per la gestione del tasking model per sistemi a processori strettamente accoppiati in cluster e poi interconnessi attraverso una network on chip. Ci siamo focalizzati sulla loro scalabilità e sul supporto di task di granularità fine, come è tipico nelle applicazioni embedded. Il secondo contributo di questa tesi è stata proporre una estensione del runtime di OpenMP che cerca di prevedere la manifestazione di errori dati da fenomeni di variability tramite una schedulazione efficiente del carico di lavoro.

Una applicazione per la valutazione delle prestazioni di architetture parallele a basso consumo

In questa tesi si descrive il lavoro svolto presso l’istituto INFN-CNAF, che consiste nello sviluppo di un’applicazione parallela e del suo utilizzo su di un’architettura a basso consumo, allo scopo di valutare il comportamento della stessa, confrontandolo a quello di architetture ad alta potenza di calcolo. L’architettura a basso consumo utilizzata `e un system on chip mutuato dal mondo mobile e embedded contenente una cpu ARM quad core e una GPU NVIDIA, mentre l’architettura ad alta potenza di calcolo `e un sistema x86 64 con una GPU NVIDIA di classe server. L’applicazione `e stata sviluppata in C++ in due differenti versioni: la prima utilizzando l’estensione OpenMP e la seconda utilizzando l’estensione CUDA. Queste due versioni hanno permesso di valutare il comportamento dell’architettura a basso consumo sotto diversi punti di vista, utilizzando nelle differenti versioni dell’applicazione la CPU o la GPU come unita` principale di elaborazione.

Modelling, simulation and characterization of epithelial cell culture biochip

A microfluidic Organ-on-Chip has been developed for monitoring the epithelial cells monolayer. Equivalent circuit Model was used to determine the electrical properties from the impedance spectra of the epithelial cells monolayer. Black platinum on platinum electrodes was electrochemically deposited onto the surface of electrodes to reduce the influence of the electrical double layer on the impedance measurements. Measurements of impedance with an Impedance Analyzer were done to validate the equivalent circuit model and the decrease of the double layer effect. A Lock-in Amplifier was designed to measure the impedance.

Microphysiological systems: Nuove piattaforme di coltura cellulare per applicazioni di interesse biomedico

In questo elaborato verranno presentati le finalità, gli sviluppi e le prospettive future di una tipologia di coltura cellulare, ovvero dei microphysiological systems - MPS (o organs-on-chips), nuovi microdispositivi atti a riprodorre il più fedelmente possibile le condizioni fisiologiche adatte per la crescita e il mantenimento di strutture cellulari complesse. Verranno quindi inizialmente descritte le specifiche di base di questi dispositivi, sottolineandone l'innovatività dal punto di vista tecnologico e funzionale. Grazie agli MPS è infatti stato possibile intraprendere studi per una migliore comprensione del comportamento in condizioni dinamiche di una vasta gamma di tessuti, e la risposta di questi a stimoli chimici e fisici, rappresentativi di condizioni fisiologiche o patologiche, aprendo così le porte a nuovi standard per la sperimentazione clinica. Verrà quindi proposto un caso di studio, che riguarda l'applicazione di quanto sopra all'ambito cardiocircolatorio, prendendo in esame un modello di heart-on-a-chip, descrivendolo in tutte le fasi della sua realizzazione e infine discutendo uno studio riguardante la risposta delle cellule del muscolo cardiaco a un trattamento farmacologico.

Sistema di visione stereo su architettura ZYNQ

Lo scopo della tesi è creare un’architettura in FPGA in grado di ricavare informazioni 3D da una coppia di sensori stereo. La pipeline è stata realizzata utilizzando il System-on-Chip Zynq, che permette una stretta interazione tra la parte hardware realizzata in FPGA e la CPU. Dopo uno studio preliminare degli strumenti hardware e software, è stata realizzata l’architettura base per la scrittura e la lettura di immagini nella memoria DDR dello Zynq. In seguito l’attenzione si è spostata sull’implementazione di algoritmi stereo (rettificazione e stereo matching) su FPGA e nella realizzazione di una pipeline in grado di ricavare accurate mappe di disparità in tempo reale acquisendo le immagini da una camera stereo.

Large-scale Network Analysis on Distributed Architectures

Questa dissertazione esamina le sfide e i limiti che gli algoritmi di analisi di grafi incontrano in architetture distribuite costituite da personal computer. In particolare, analizza il comportamento dell'algoritmo del PageRank così come implementato in una popolare libreria C++ di analisi di grafi distribuiti, la Parallel Boost Graph Library (Parallel BGL). I risultati qui presentati mostrano che il modello di programmazione parallela Bulk Synchronous Parallel è inadatto all'implementazione efficiente del PageRank su cluster costituiti da personal computer. L'implementazione analizzata ha infatti evidenziato una scalabilità negativa, il tempo di esecuzione dell'algoritmo aumenta linearmente in funzione del numero di processori. Questi risultati sono stati ottenuti lanciando l'algoritmo del PageRank della Parallel BGL su un cluster di 43 PC dual-core con 2GB di RAM l'uno, usando diversi grafi scelti in modo da facilitare l'identificazione delle variabili che influenzano la scalabilità. Grafi rappresentanti modelli diversi hanno dato risultati differenti, mostrando che c'è una relazione tra il coefficiente di clustering e l'inclinazione della retta che rappresenta il tempo in funzione del numero di processori. Ad esempio, i grafi Erdős–Rényi, aventi un basso coefficiente di clustering, hanno rappresentato il caso peggiore nei test del PageRank, mentre i grafi Small-World, aventi un alto coefficiente di clustering, hanno rappresentato il caso migliore. Anche le dimensioni del grafo hanno mostrato un'influenza sul tempo di esecuzione particolarmente interessante. Infatti, si è mostrato che la relazione tra il numero di nodi e il numero di archi determina il tempo totale.

Tactile Perception - Perception of tactile distance on a single skin surface changes with stimulus orientation: a neuronal network modelling study

L’interazione che abbiamo con l’ambiente che ci circonda dipende sia da diverse tipologie di stimoli esterni che percepiamo (tattili, visivi, acustici, ecc.) sia dalla loro elaborazione per opera del nostro sistema nervoso. A volte però, l’integrazione e l’elaborazione di tali input possono causare effetti d’illusione. Ciò si presenta, ad esempio, nella percezione tattile. Infatti, la percezione di distanze tattili varia al variare della regione corporea considerata. Il concetto che distanze sulla cute siano frequentemente erroneamente percepite, è stato scoperto circa un secolo fa da Weber. In particolare, una determinata distanza fisica, è percepita maggiore su parti del corpo che presentano una più alta densità di meccanocettori rispetto a distanze applicate su parti del corpo con inferiore densità. Oltre a questa illusione, un importante fenomeno osservato in vivo è rappresentato dal fatto che la percezione della distanza tattile dipende dall’orientazione degli stimoli applicati sulla cute. In sostanza, la distanza percepita su una regione cutanea varia al variare dell’orientazione degli stimoli applicati. Recentemente, Longo e Haggard (Longo & Haggard, J.Exp.Psychol. Hum Percept Perform 37: 720-726, 2011), allo scopo di investigare come sia rappresentato il nostro corpo all’interno del nostro cervello, hanno messo a confronto distanze tattili a diverse orientazioni sulla mano deducendo che la distanza fra due stimoli puntuali è percepita maggiore se applicata trasversalmente sulla mano anziché longitudinalmente. Tale illusione è nota con il nome di Illusione Tattile Orientazione-Dipendente e diversi risultati riportati in letteratura dimostrano che tale illusione dipende dalla distanza che intercorre fra i due stimoli puntuali sulla cute. Infatti, Green riporta in un suo articolo (Green, Percpept Pshycophys 31, 315-323, 1982) il fatto che maggiore sia la distanza applicata e maggiore risulterà l’effetto illusivo che si presenta. L’illusione di Weber e l’illusione tattile orientazione-dipendente sono spiegate in letteratura considerando differenze riguardanti la densità di recettori, gli effetti di magnificazione corticale a livello della corteccia primaria somatosensoriale (regioni della corteccia somatosensoriale, di dimensioni differenti, sono adibite a diverse regioni corporee) e differenze nella dimensione e forma dei campi recettivi. Tuttavia tali effetti di illusione risultano molto meno rilevanti rispetto a quelli che ci si aspetta semplicemente considerando i meccanismi fisiologici, elencati in precedenza, che li causano. Ciò suggerisce che l’informazione tattile elaborata a livello della corteccia primaria somatosensoriale, riceva successivi step di elaborazione in aree corticali di più alto livello. Esse agiscono allo scopo di ridurre il divario fra distanza percepita trasversalmente e distanza percepita longitudinalmente, rendendole più simili tra loro. Tale processo assume il nome di “Rescaling Process”. I meccanismi neurali che operano nel cervello allo scopo di garantire Rescaling Process restano ancora largamente sconosciuti. Perciò, lo scopo del mio progetto di tesi è stato quello di realizzare un modello di rete neurale che simulasse gli aspetti riguardanti la percezione tattile, l’illusione orientazione-dipendente e il processo di rescaling avanzando possibili ipotesi circa i meccanismi neurali che concorrono alla loro realizzazione. Il modello computazionale si compone di due diversi layers neurali che processano l’informazione tattile. Uno di questi rappresenta un’area corticale di più basso livello (chiamata Area1) nella quale una prima e distorta rappresentazione tattile è realizzata. Per questo, tale layer potrebbe rappresentare un’area della corteccia primaria somatosensoriale, dove la rappresentazione della distanza tattile è significativamente distorta a causa dell’anisotropia dei campi recettivi e della magnificazione corticale. Il secondo layer (chiamato Area2) rappresenta un’area di più alto livello che riceve le informazioni tattili dal primo e ne riduce la loro distorsione mediante Rescaling Process. Questo layer potrebbe rappresentare aree corticali superiori (ad esempio la corteccia parietale o quella temporale) adibite anch’esse alla percezione di distanze tattili ed implicate nel Rescaling Process. Nel modello, i neuroni in Area1 ricevono informazioni dagli stimoli esterni (applicati sulla cute) inviando quindi informazioni ai neuroni in Area2 mediante sinapsi Feed-forward eccitatorie. Di fatto, neuroni appartenenti ad uno stesso layer comunicano fra loro attraverso sinapsi laterali aventi una forma a cappello Messicano. E’ importante affermare che la rete neurale implementata è principalmente un modello concettuale che non si preme di fornire un’accurata riproduzione delle strutture fisiologiche ed anatomiche. Per questo occorre considerare un livello astratto di implementazione senza specificare un’esatta corrispondenza tra layers nel modello e regioni anatomiche presenti nel cervello. Tuttavia, i meccanismi inclusi nel modello sono biologicamente plausibili. Dunque la rete neurale può essere utile per una migliore comprensione dei molteplici meccanismi agenti nel nostro cervello, allo scopo di elaborare diversi input tattili. Infatti, il modello è in grado di riprodurre diversi risultati riportati negli articoli di Green e Longo & Haggard.

On the Design of a Boolean-network Robot Swarm: Collective Recognition of Ground Patterns.

Uno dei principali ambiti di ricerca dell’intelligenza artificiale concerne la realizzazione di agenti (in particolare, robot) in grado di aiutare o sostituire l’uomo nell’esecuzione di determinate attività. A tal fine, è possibile procedere seguendo due diversi metodi di progettazione: la progettazione manuale e la progettazione automatica. Quest’ultima può essere preferita alla prima nei contesti in cui occorra tenere in considerazione requisiti quali flessibilità e adattamento, spesso essenziali per lo svolgimento di compiti non banali in contesti reali. La progettazione automatica prende in considerazione un modello col quale rappresentare il comportamento dell’agente e una tecnica di ricerca (oppure di apprendimento) che iterativamente modifica il modello al fine di renderlo il più adatto possibile al compito in esame. In questo lavoro, il modello utilizzato per la rappresentazione del comportamento del robot è una rete booleana (Boolean network o Kauffman network). La scelta di tale modello deriva dal fatto che possiede una semplice struttura che rende agevolmente studiabili le dinamiche tuttavia complesse che si manifestano al suo interno. Inoltre, la letteratura recente mostra che i modelli a rete, quali ad esempio le reti neuronali artificiali, si sono dimostrati efficaci nella programmazione di robot. La metodologia per l’evoluzione di tale modello riguarda l’uso di tecniche di ricerca meta-euristiche in grado di trovare buone soluzioni in tempi contenuti, nonostante i grandi spazi di ricerca. Lavori precedenti hanno gia dimostrato l’applicabilità e investigato la metodologia su un singolo robot. Lo scopo di questo lavoro è quello di fornire prova di principio relativa a un insieme di robot, aprendo nuove strade per la progettazione in swarm robotics. In questo scenario, semplici agenti autonomi, interagendo fra loro, portano all’emergere di un comportamento coordinato adempiendo a task impossibili per la singola unità. Questo lavoro fornisce utili ed interessanti opportunità anche per lo studio delle interazioni fra reti booleane. Infatti, ogni robot è controllato da una rete booleana che determina l’output in funzione della propria configurazione interna ma anche dagli input ricevuti dai robot vicini. In questo lavoro definiamo un task in cui lo swarm deve discriminare due diversi pattern sul pavimento dell’arena utilizzando solo informazioni scambiate localmente. Dopo una prima serie di esperimenti preliminari che hanno permesso di identificare i parametri e il migliore algoritmo di ricerca, abbiamo semplificato l’istanza del problema per meglio investigare i criteri che possono influire sulle prestazioni. E’ stata così identificata una particolare combinazione di informazione che, scambiata localmente fra robot, porta al miglioramento delle prestazioni. L’ipotesi è stata confermata applicando successivamente questo risultato ad un’istanza più difficile del problema. Il lavoro si conclude suggerendo nuovi strumenti per lo studio dei fenomeni emergenti in contesti in cui le reti booleane interagiscono fra loro.

Implementation of network entropy algorithms on hpc machines, with application to high-dimensional experimental data

Network Theory is a prolific and lively field, especially when it approaches Biology. New concepts from this theory find application in areas where extensive datasets are already available for analysis, without the need to invest money to collect them. The only tools that are necessary to accomplish an analysis are easily accessible: a computing machine and a good algorithm. As these two tools progress, thanks to technology advancement and human efforts, wider and wider datasets can be analysed. The aim of this paper is twofold. Firstly, to provide an overview of one of these concepts, which originates at the meeting point between Network Theory and Statistical Mechanics: the entropy of a network ensemble. This quantity has been described from different angles in the literature. Our approach tries to be a synthesis of the different points of view. The second part of the work is devoted to presenting a parallel algorithm that can evaluate this quantity over an extensive dataset. Eventually, the algorithm will also be used to analyse high-throughput data coming from biology.

Laplace operator on finite graphs and a network diffusion model for the progression of the Alzheimer disease

Nella tesi viene descritto il Network Diffusion Model, ovvero il modello di A. Ray, A. Kuceyeski, M. Weiner inerente i meccanismi di progressione della demenza senile. In tale modello si approssima l'encefalo sano con una rete cerebrale (ovvero un grafo pesato), si identifica un generale fattore di malattia e se ne analizza la propagazione che avviene secondo meccanismi analoghi a quelli di un'infezione da prioni. La progressione del fattore di malattia e le conseguenze macroscopiche di tale processo(tra cui principalmente l'atrofia corticale) vengono, poi, descritte mediante approccio matematico. I risultati teoretici vengono confrontati con quanto osservato sperimentalmente in pazienti affetti da demenza senile. Nella tesi, inoltre, si fornisce una panoramica sui recenti studi inerenti i processi neurodegenerativi e si costruisce il contesto matematico di riferimento del modello preso in esame. Si presenta una panoramica sui grafi finiti, si introduce l'operatore di Laplace sui grafi e si forniscono stime dall'alto e dal basso per gli autovalori. Al fine di costruire una cornice matematica completa si analizza la relazione tra caso discreto e continuo: viene descritto l'operatore di Laplace-Beltrami sulle varietà riemanniane compatte e vengono fornite stime dall'alto per gli autovalori dell'operatore di Laplace-Beltrami associato a tali varietà a partire dalle stime dall'alto per gli autovalori del laplaciano sui grafi finiti.