Constraint based methods for allocation and scheduling of periodic applications

This work presents exact algorithms for the Resource Allocation and Cyclic Scheduling Problems (RA&CSPs). Cyclic Scheduling Problems arise in a number of application areas, such as in hoist scheduling, mass production, compiler design (implementing scheduling loops on parallel architectures), software pipelining, and in embedded system design. The RA&CS problem concerns time and resource assignment to a set of activities, to be indefinitely repeated, subject to precedence and resource capacity constraints. In this work we present two constraint programming frameworks facing two different types of cyclic problems. In first instance, we consider the disjunctive RA&CSP, where the allocation problem considers unary resources. Instances are described through the Synchronous Data-flow (SDF) Model of Computation. The key problem of finding a maximum-throughput allocation and scheduling of Synchronous Data-Flow graphs onto a multi-core architecture is NP-hard and has been traditionally solved by means of heuristic (incomplete) algorithms. We propose an exact (complete) algorithm for the computation of a maximum-throughput mapping of applications specified as SDFG onto multi-core architectures. Results show that the approach can handle realistic instances in terms of size and complexity. Next, we tackle the Cyclic Resource-Constrained Scheduling Problem (i.e. CRCSP). We propose a Constraint Programming approach based on modular arithmetic: in particular, we introduce a modular precedence constraint and a global cumulative constraint along with their filtering algorithms. Many traditional approaches to cyclic scheduling operate by fixing the period value and then solving a linear problem in a generate-and-test fashion. Conversely, our technique is based on a non-linear model and tackles the problem as a whole: the period value is inferred from the scheduling decisions. The proposed approaches have been tested on a number of non-trivial synthetic instances and on a set of realistic industrial instances achieving good results on practical size problem.

Valutazione dello spostamento tridimensionale degli impianti in giovani pazienti affetti da EDs riabilitati con overdenture implanto-supportati

Ectodermal Dysplasias syndrome (EDs) are a heterogeneous group of inherited disorders characterized by dysplasia of tissues of ectodermal origin. Complete or partial anodontia are the most frequent dental findings. Prosthetic rehabilitation is recommended from functional, esthetic, and psychological points of view. Because of the anatomical abnormalities of existing teeth and alveolar ridges, conventional prosthetic rehabilitation in young patient is often difficult. Five growing patients (age 9 to 11 years) with oligo- or anodontia were prosthetically rehabilitated. Panoramic film and Cone Bean Computerized Tomography were performed and a resin model of mandibular bone was made. Despite a remarkable multi-dimensional atrophy of the alveolar bone, the insertion of two tapered implants was possible. After a submerged healing period of 2 month, the implants were exposed and abutment connection was performed. Implants were connected with an expansion bar that permits mandibular growth and prosthetic retention. A removable prosthesis was constructed with ball attachments. Mandibular growth was followed and evaluated using the expansion guide and cephalometric radiographs. Mandibular growth in sagittal and transverse direction had no adverse effects on implant position. The expansion bar permitted the undisturbed growth of the mandible. After 4.5 years of follow-up, this study showed that Implant-supported overdenture may improve oral function, phonesis and esthetics. The mandibular rotation accompanying growth had not caused a significant problem relative to the angulation and migration of the implants. Implants can be successfully placed, restored and loaded in growing EDs patients. The cephalometric analysis supported that EDs patients show midface hypoplasia with a class III tendency, which can be avoided by early rehabilitation. Thanks to the good stability and retention of the implant-supported overdenture, patients considered the prostheses as comparable to natural teeth.

Context-aware wireless networks

This thesis investigates context-aware wireless networks, capable to adapt their behavior to the context and the application, thanks to the ability of combining communication, sensing and localization. Problems of signals demodulation, parameters estimation and localization are addressed exploiting analytical methods, simulations and experimentation, for the derivation of the fundamental limits, the performance characterization of the proposed schemes and the experimental validation. Ultrawide-bandwidth (UWB) signals are in certain cases considered and non-coherent receivers, allowing the exploitation of the multipath channel diversity without adopting complex architectures, investigated. Closed-form expressions for the achievable bit error probability of novel proposed architectures are derived. The problem of time delay estimation (TDE), enabling network localization thanks to ranging measurement, is addressed from a theoretical point of view. New fundamental bounds on TDE are derived in the case the received signal is partially known or unknown at receiver side, as often occurs due to propagation or due to the adoption of low-complexity estimators. Practical estimators, such as energy-based estimators, are revised and their performance compared with the new bounds. The localization issue is addressed with experimentation for the characterization of cooperative networks. Practical algorithms able to improve the accuracy in non-line-of-sight (NLOS) channel conditions are evaluated on measured data. With the purpose of enhancing the localization coverage in NLOS conditions, non-regenerative relaying techniques for localization are introduced and ad hoc position estimators are devised. An example of context-aware network is given with the study of the UWB-RFID system for detecting and locating semi-passive tags. In particular a deep investigation involving low-complexity receivers capable to deal with problems of multi-tag interference, synchronization mismatches and clock drift is presented. Finally, theoretical bounds on the localization accuracy of this and others passive localization networks (e.g., radar) are derived, also accounting for different configurations such as in monostatic and multistatic networks.

A clustering method for robust and reliable large scale functional and structural protein sequence annotation

Bioinformatics, in the last few decades, has played a fundamental role to give sense to the huge amount of data produced. Obtained the complete sequence of a genome, the major problem of knowing as much as possible of its coding regions, is crucial. Protein sequence annotation is challenging and, due to the size of the problem, only computational approaches can provide a feasible solution. As it has been recently pointed out by the Critical Assessment of Function Annotations (CAFA), most accurate methods are those based on the transfer-by-homology approach and the most incisive contribution is given by cross-genome comparisons. In the present thesis it is described a non-hierarchical sequence clustering method for protein automatic large-scale annotation, called “The Bologna Annotation Resource Plus” (BAR+). The method is based on an all-against-all alignment of more than 13 millions protein sequences characterized by a very stringent metric. BAR+ can safely transfer functional features (Gene Ontology and Pfam terms) inside clusters by means of a statistical validation, even in the case of multi-domain proteins. Within BAR+ clusters it is also possible to transfer the three dimensional structure (when a template is available). This is possible by the way of cluster-specific HMM profiles that can be used to calculate reliable template-to-target alignments even in the case of distantly related proteins (sequence identity < 30%). Other BAR+ based applications have been developed during my doctorate including the prediction of Magnesium binding sites in human proteins, the ABC transporters superfamily classification and the functional prediction (GO terms) of the CAFA targets. Remarkably, in the CAFA assessment, BAR+ placed among the ten most accurate methods. At present, as a web server for the functional and structural protein sequence annotation, BAR+ is freely available at http://bar.biocomp.unibo.it/bar2.0.

Metodi euristici per il problema dei trasporti con costi fissi

In questa tesi viene considerato il problema dei trasporti con costi fissi (FCTP) che, assieme al Traveling Salesman Problem (TSP), è uno dei problemi nobili dell’ottimizzazione combinatoria. Esso generalizza il ben noto problema dei trasporti (TP) imponendo che il costo per spedire prodotti da un’origine ad una destinazione sia composto da un costo fisso ed un costo proporzionale alla quantità spedita. Il FCTP è stato formulato per la prima volta in un articolo di Hirsch e Dantzig (1968) ed è stato da allora oggetto di studio per la ricerca di nuovi e sempre migliori algoritmi di risoluzione. Nessuno dei metodi esatti fin ora pubblicati è in grado di risolvere istanze con più di 15 origini e 15 destinazioni. Solo recentemente, Roberti et al. (2013), in un paper in corso di pubblicazione, hanno presentato un metodo esatto basato su una nuova formulazione matematica del problema, il quale è in grado di risolvere istanze di FCTP con 70 origini e 70 destinazioni. La crescita esponenziale dello sforzo computazionale richiesto dai metodi esatti ne ha confinato l’applicazione a problemi di dimensioni ridotte. Tali limitazioni hanno portato allo studio e alla ricerca di approcci approssimativi, euristici e metaeuristici i quali sfruttano varie strategie di local search. Fra i molteplici metodi euristici presentati in letteratura, meritano particolare attenzione quelli di Sun et al. (1998) e Glover et al. (2005). Recentemente, Buson et al. (2013) hanno presentato un nuovo euristico che domina tutti i precedenti sui problemi test proposti in letteratura. In questa tesi viene presentato un approccio Tabu Search che migliora il metodo originalmente proposto da Sun et al. (1998). I risultati computazionali ottenuti con un codice prototipale indicano che l’algoritmo sviluppato è migliore del metodo originario di Sun et al. (1998) e competitivo con il più recente metodo proposto da Buson et al. (2013).

Alla ricerca della sostenibilità: lo sviluppo dell'agricoltura dall'Unità d'Italia alla Green Economy

L’elaborato finale presentato per la tesi di Dottorato analizza e riconduce a unitarietà, per quanto possibile, alcune delle attività di ricerca da me svolte durante questi tre anni, il cui filo conduttore è l'impatto ambientale delle attività umane e la promozione dello sviluppo sostenibile. Il mio filone di ricerca è stato improntato, dal punto di vista di politica economica, sull'analisi storica dello sviluppo del settore agricolo dall'Unità d'Italia ai giorni nostri e dei cambiamenti avvenuti in contemporanea nel contesto socio-economico e territoriale nazionale, facendo particolare riferimento alle tematiche legate ai consumi e alla dipendenza energetica ed all'impatto ambientale. Parte della mia ricerca è stata, infatti, incentrata sull'analisi dello sviluppo della Green Economy, in particolare per quanto riguarda il settore agroalimentare e la produzione di fonti di energia rinnovabile. Enfasi viene posta sia sulle politiche implementate a livello comunitario e nazionale, sia sul cambiamento dei consumi, in particolare per quanto riguarda gli acquisti di prodotti biologici. La Green Economy è vista come fattore di sviluppo e opportunità per uscire dall'attuale contesto di crisi economico-finanziaria. Crisi, che è strutturale e di carattere duraturo, affiancata da una crescente problematica ambientale dovuta all'attuale modello produttivo, fortemente dipendente dai combustibili fossili. Difatti la necessità di cambiare paradigma produttivo promuovendo la sostenibilità è visto anche in ottica di mitigazione del cambiamento climatico e dei suoi impatti socio-economici particolare dal punto di vista dei disastri ambientali. Questo punto è analizzato anche in termini di sicurezza internazionale e di emergenza umanitaria, con riferimento al possibile utilizzo da parte delle organizzazioni di intervento nei contesti di emergenza di tecnologie alimentate da energia rinnovabile. Dando così una risposta Green ad una problematica esacerbata dall'impatto dello sviluppo delle attività umane.

Non-normal modal logics, quantification, and deontic dilemmas. A study in multi-relational semantics

This dissertation is devoted to the study of non-normal (modal) systems for deontic logics, both on the propositional level, and on the first order one. In particular we developed our study the Multi-relational setting that generalises standard Kripke Semantics. We present new completeness results concerning the semantic setting of several systems which are able to handle normative dilemmas and conflicts. Although primarily driven by issues related to the legal and moral field, these results are also relevant for the more theoretical field of Modal Logic itself, as we propose a syntactical, and semantic study of intermediate systems between the classical propositional calculus CPC and the minimal normal modal logic K.

Sense of Community in contexts of multi culture

The theme “Belongingness” has a central role in the current debate on Community Psychology and in daily life. To try to understand the consequences of these changes, the research focuses on the concept of Sense of Community. In fact, Sense of Community has always been a central tool (Sarason, 1974; MacMillan & Chavis, 1986) to study communities (McMillan, 2011; Nowell & Boyd, 2011) and for a long time has represented positive values and something to aspire to. However, current debates indicate that Sense of Community is an outmoded concept and underline the problematic issue of “promotion of Sense of Community” in contexts of multi culture. The aim of the present research is to analyze Sense of Community in context of multi culture, as we consider that it can still be a fundamental tool to study and understand communities. In particular we are interested in understanding the role of Multiple Sense of Community (Brodsky, 2009) on Identity and Wellbeing (and its dimensions). We focused on a specific context, the Station Zone in Reggio Emilia, that is characterized by high levels of cultural diversity and different social problems (Giovannini & Vezzali, 2011). The research is developed and divided into two parts. The first part consists of an exploratory qualitative study that analyzes meanings of community among leaders of different ethnic groups living in the Station Zone. The second part consists of a “General Model” study and four parallel studies to analyze Multiple Sense of Community in different ethnic groups (Albanians, Moroccans, Chinese and Italians. The results indicate the different role of Multiple SOC in the relation between Identity and Wellbeing, in particular the relevance of Relational SOC and its different implications. Moreover, the factor “culture” represents an significant element in order to consider differences among ethnic groups.

Use of shared memory in the context of embedded multi-core processors: exploration of the technology and its limits

Modern embedded systems embrace many-core shared-memory designs. Due to constrained power and area budgets, most of them feature software-managed scratchpad memories instead of data caches to increase the data locality. It is therefore programmers’ responsibility to explicitly manage the memory transfers, and this make programming these platform cumbersome. Moreover, complex modern applications must be adequately parallelized before they can the parallel potential of the platform into actual performance. To support this, programming languages were proposed, which work at a high level of abstraction, and rely on a runtime whose cost hinders performance, especially in embedded systems, where resources and power budget are constrained. This dissertation explores the applicability of the shared-memory paradigm on modern many-core systems, focusing on the ease-of-programming. It focuses on OpenMP, the de-facto standard for shared memory programming. In a first part, the cost of algorithms for synchronization and data partitioning are analyzed, and they are adapted to modern embedded many-cores. Then, the original design of an OpenMP runtime library is presented, which supports complex forms of parallelism such as multi-level and irregular parallelism. In the second part of the thesis, the focus is on heterogeneous systems, where hardware accelerators are coupled to (many-)cores to implement key functional kernels with orders-of-magnitude of speedup and energy efficiency compared to the “pure software” version. However, three main issues rise, namely i) platform design complexity, ii) architectural scalability and iii) programmability. To tackle them, a template for a generic hardware processing unit (HWPU) is proposed, which share the memory banks with cores, and the template for a scalable architecture is shown, which integrates them through the shared-memory system. Then, a full software stack and toolchain are developed to support platform design and to let programmers exploiting the accelerators of the platform. The OpenMP frontend is extended to interact with it.

Experimental Analysis and Numerical Simulation of Quench in Superconducting HTS Tapes and Coils

The quench characteristics of second generation (2 G) YBCO Coated Conductor (CC) tapes are of fundamental importance for the design and safe operation of superconducting cables and magnets based on this material. Their ability to transport high current densities at high temperature, up to 77 K, and at very high fields, over 20 T, together with the increasing knowledge in their manufacturing, which is reducing their cost, are pushing the use of this innovative material in numerous system applications, from high field magnets for research to motors and generators as well as for cables. The aim of this Ph. D. thesis is the experimental analysis and numerical simulations of quench in superconducting HTS tapes and coils. A measurements facility for the characterization of superconducting tapes and coils was designed, assembled and tested. The facility consist of a cryostat, a cryocooler, a vacuum system, resistive and superconducting current leads and signal feedthrough. Moreover, the data acquisition system and the software for critical current and quench measurements were developed. A 2D model was developed using the finite element code COMSOL Multiphysics R . The problem of modeling the high aspect ratio of the tape is tackled by multiplying the tape thickness by a constant factor, compensating the heat and electrical balance equations by introducing a material anisotropy. The model was then validated both with the results of a 1D quench model based on a non-linear electric circuit coupled to a thermal model of the tape, to literature measurements and to critical current and quench measurements made in the cryogenic facility. Finally the model was extended to the study of coils and windings with the definition of the tape and stack homogenized properties. The procedure allows the definition of a multi-scale hierarchical model, able to simulate the windings with different degrees of detail.

Techniques and Methods for a multi-scale analysis of neuromuscular fatigue

This thesis proposes an integrated holistic approach to the study of neuromuscular fatigue in order to encompass all the causes and all the consequences underlying the phenomenon. Starting from the metabolic processes occurring at the cellular level, the reader is guided toward the physiological changes at the motorneuron and motor unit level and from this to the more general biomechanical alterations. In Chapter 1 a list of the various definitions for fatigue spanning several contexts has been reported. In Chapter 2, the electrophysiological changes in terms of motor unit behavior and descending neural drive to the muscle have been studied extensively as well as the biomechanical adaptations induced. In Chapter 3 a study based on the observation of temporal features extracted from sEMG signals has been reported leading to the need of a more robust and reliable indicator during fatiguing tasks. Therefore, in Chapter 4, a novel bi-dimensional parameter is proposed. The study on sEMG-based indicators opened a scenario also on neurophysiological mechanisms underlying fatigue. For this purpose, in Chapter 5, a protocol designed for the analysis of motor unit-related parameters during prolonged fatiguing contractions is presented. In particular, two methodologies have been applied to multichannel sEMG recordings of isometric contractions of the Tibialis Anterior muscle: the state-of-the-art technique for sEMG decomposition and a coherence analysis on MU spike trains. The importance of a multi-scale approach has been finally highlighted in the context of the evaluation of cycling performance, where fatigue is one of the limiting factors. In particular, the last chapter of this thesis can be considered as a paradigm: physiological, metabolic, environmental, psychological and biomechanical factors influence the performance of a cyclist and only when all of these are kept together in a novel integrative way it is possible to derive a clear model and make correct assessments.

Obsessed With Work: A multi-causal and multi-rater approach to workaholism

Workaholism is defined as the combination of two underlying dimensions: working excessively and working compulsively. The present thesis aims at achieving the following purposes: 1) to test whether the interaction between environmental and personal antecedents may enhance workaholism; 2) to develop a questionnaire aimed to assess overwork climate in the workplace; 3) to contrast focal employees’ and coworkers’ perceptions of employees’ workaholism and engagement. Concerning the first purpose, the interaction between overwork climate and person characteristics (achievement motivation, perfectionism, conscientiousness, self-efficacy) was explored on a sample of 333 Dutch employees. The results of moderated regression analyses showed that the interaction between overwork climate and person characteristics is related to workaholism. The second purpose was pursued with two interrelated studies. In Study 1 the Overwork Climate Scale (OWCS) was developed and tested using a principal component analysis (N = 395) and a confirmatory factor analysis (N = 396). Two overwork climate dimensions were distinguished, overwork endorsement and lacking overwork rewards. In Study 2 the total sample (N = 791) was used to explore the association of overwork climate with two types of working hard: work engagement and workaholism. Lacking overwork rewards was negatively associated with engagement, whereas overwork endorsement showed a positive association with workaholism. Concerning the third purpose, using a sample of 73 dyads composed by focal employees and their coworkers, a multitrait-multimethod matrix and a correlated trait-correlated method model, i.e. the CT-C(M–1) model, were examined. Our results showed a considerable agreement between raters on focal employees' engagement and workaholism. In contrast, we observed a significant difference concerning the cognitive dimension of workaholism, working compulsively. Moreover, we provided further evidence for the discriminant validity between engagement and workaholism. Overall, workaholism appears as a negative work-related state that could be better explained by assuming a multi-causal and multi-rater approach.

Identity dynamics and the emergence of new organizational arrangements: A multi-level study

Organizational and institutional scholars have advocated the need to examine how processes originating at an individual level can change organizations or even create new organizational arrangements able to affect institutional dynamics (Chreim et al., 2007; Powell & Colyvas, 2008; Smets et al., 2012). Conversely, research on identity work has mainly investigated the different ways individuals can modify the boundaries of their work in actual occupations, thus paying particular attention to ‘internal’ self-crafting (e.g. Wrzesniewski & Dutton, 2001). Drawing from literatures on possible and alternative self and on positive organizational scholarship (e.g., Obodaru, 2012; Roberts & Dutton, 2009), my argument is that individuals’ identity work can go well beyond the boundaries of internal self-crafting to the creation of new organizational arrangements. In this contribution I analyze, through multiple case studies, healthcare professionals who spontaneously participated in the creation of new organizational arrangements, namely health structures called Community Hospitals. The contribution develops this form of identity work by building a grounded model. My findings disclose the process that leads from the search for the enactment of different self-concepts to positive identities, through the creation of a new organizational arrangement. I contend that this is a particularly complex form of collective identity work because it requires, to be successful, concerted actions of several internal, external and institutional actors, and it also requires balanced tensions that – at the same time - enable individuals’ aspirations and organizational equilibrium. I name this process organizational collective crafting. Moreover I inquire the role of context in supporting the triggering power of those unrealized selves. I contribute to the comprehension of the consequences of self-comparisons, organizational identity variance, and positive identity. The study bears important insights on how identity work originating from individuals can influence organizational outcomes and larger social systems.

Per un'archeologia del lavoro in eta' protobizantina. Organizzazione e committenza del cantiere edilizio attraverso i marchi dei marmorari

La ricerca riguarda lo studio del cantiere edilizio protobizantino, con particolare riferimento al ciclo della lavorazione del marmo. Quest’ultimo viene analizzato sotto il profilo amministrativo, tecnico, sociale ed artigianale. L’elemento guida della ricerca sono i marchi dei marmorari, sigle apposte da funzionari e maestranze durante il processo produttivo. Dapprima, fonti letterarie ed epigrafiche, tra cui le sigle di cava e officina su marmo, vengono esaminate per ricostruire il sistema alto-imperiale di amministrazione delle cave e di gestione dei flussi marmorei, nonché l’iter tecnico-artigianale adottato per la produzione dei manufatti. Il confronto con i dati disponibili per la tarda antichità, con particolare riferimento alle cave di Proconneso, evidenzia una sostanziale continuità della prassi burocratico-amministrativa, mentre alcuni cambiamenti si riscontrano nell’ambito produttivo-artigianale. Il funzionamento degli atelier marmorari viene approfondito attraverso lo studio dei marchi dei marmorari. Si tratta di caratteri greci singoli, multipli o monogrammi. Una ricognizione sistematica delle sigle dalla pars Orientalis dell’impero, reperite in bibliografia o da ricognizioni autoptiche, ha portato alla raccolta di circa 2360 attestazioni. Per esse si propone una classificazione tipologica tra sigle di cava, stoccaggio, officina. Tra le sigle di cava si annoverano sigle di controllo, destinazione/committenza, assemblaggio/posizionamento. Una particolare attenzione è riservata alle sigle di officina, riferibili ad un nome proprio di persona, ovvero al πρωτομαΐστωρ, il capo-bottega che supervisionava il lavoro dei propri artigiani e fungeva da garante del prodotto consegnato alla committenza. Attraverso lo studio comparato delle sigle reperite a Costantinopoli e in altri contesti si mette in luce la prassi operativa adottata dagli atelier nei processi di manifattura, affrontando anche il problema delle maestranze itineranti. Infine, sono analizzate fonti scritte di varia natura per poter collocare il fenomeno del marmo in un contesto socio-economico più ampio, con particolare riferimento alle figure professionali ed artigianali coinvolte nei cantieri e al problema della committenza.

Essays on the Axiomatic Theory of Matching

This dissertation mimics the Turkish college admission procedure. It started with the purpose to reduce the inefficiencies in Turkish market. For this purpose, we propose a mechanism under a new market structure; as we prefer to call, semi-centralization. In chapter 1, we give a brief summary of Matching Theory. We present the first examples in Matching history with the most general papers and mechanisms. In chapter 2, we propose our mechanism. In real life application, that is in Turkish university placements, the mechanism reduces the inefficiencies of the current system. The success of the mechanism depends on the preference profile. It is easy to show that under complete information the mechanism implements the full set of stable matchings for a given profile. In chapter 3, we refine our basic mechanism. The modification on the mechanism has a crucial effect on the results. The new mechanism is, as we call, a middle mechanism. In one of the subdomain, this mechanism coincides with the original basic mechanism. But, in the other partition, it gives the same results with Gale and Shapley's algorithm. In chapter 4, we apply our basic mechanism to well known Roommate Problem. Since the roommate problem is in one-sided game patern, firstly we propose an auxiliary function to convert the game semi centralized two-sided game, because our basic mechanism is designed for this framework. We show that this process is succesful in finding a stable matching in the existence of stability. We also show that our mechanism easily and simply tells us if a profile lacks of stability by using purified orderings. Finally, we show a method to find all the stable matching in the existence of multi stability. The method is simply to run the mechanism for all of the top agents in the social preference.