Gravity-based Local Clock Synchronization in Wireless Sensor Networks

Contention-based MAC protocols follow periodic listen/sleep cycles. These protocols face the problem of virtual clustering if different unsynchronized listen/sleep schedules occur in the network, which has been shown to happen in wireless sensor networks. To interconnect these virtual clusters, border nodes maintaining all respective listen/sleep schedules are required. However, this is a waste of energy, if locally a common schedule can be determined. We propose to achieve local synchronization with a mechanism that is similar to gravitation. Clusters represent the mass, whereas synchronization messages sent by each cluster represent the gravitation force of the according cluster. Due to the mutual attraction caused by the clusters, all clusters merge finally. The exchange of synchronization messages itself is not altered by LACAS. Accordingly, LACAS introduces no overhead. Only a not yet used property of synchronization mechanisms is exploited.

Non-preemptive and SRP-based fullypreemptive scheduling of real-time Software Transactional Memory

Recent embedded processor architectures containing multiple heterogeneous cores and non-coherent caches renewed attention to the use of Software Transactional Memory (STM) as a building block for developing parallel applications. STM promises to ease concurrent and parallel software development, but relies on the possibility of abort conflicting transactions to maintain data consistency, which in turns affects the execution time of tasks carrying transactions. Because of this fact the timing behaviour of the task set may not be predictable, thus it is crucial to limit the execution time overheads resulting from aborts. In this paper we formalise a FIFO-based algorithm to order the sequence of commits of concurrent transactions. Then, we propose and evaluate two non-preemptive and one SRP-based fully-preemptive scheduling strategies, in order to avoid transaction starvation.

Avaliação dos mecanismos de concorrência na API do Java 8

As plataformas com múltiplos núcleos tornaram a programação paralela/concorrente num tópico de interesse geral. Diversos modelos de programação têm vindo a ser propostos, facilitando aos programadores a identificação de regiões de código potencialmente paralelizáveis, deixando ao sistema operativo a tarefa de as escalonar dinamicamente em tempo de execução, explorando o maior grau possível de paralelismo. O Java não foge a esta tendência, disponibilizando ao programador um número crescente de bibliotecas de mecanismos de sincronização e paralelização de código. Neste contexto, esta tese apresenta e discute um conjunto de resultados obtidos através de testes intensivos à eficiência de algoritmos de ordenação implementados com recurso aos mecanismos de concorrência da API do Java 8 (Threads, Threadpools, ExecutorService, CountdownLach, ExecutorCompletionService e ForkJoinPools) em sistemas com um número de núcleos variável. Para cada um dos mecanismos, são apresentadas conclusões sobre o seu funcionamento e discutidos os cenários em que o seu uso pode ser rentabilizado de modo a serem obtidos melhores tempos de execução.

Brain dynamics sustaining rapid rule extraction from speech

Language acquisition is a complex process that requires the synergic involvement of different cognitive functions, which include extracting and storing the words of the language and their embedded rules for progressive acquisition of grammatical information. As has been shown in other fields that study learning processes, synchronization mechanisms between neuronal assemblies might have a key role during language learning. In particular, studying these dynamics may help uncover whether different oscillatory patterns sustain more item-based learning of words and rule-based learning from speech input. Therefore, we tracked the modulation of oscillatory neural activity during the initial exposure to an artificial language, which contained embedded rules. We analyzed both spectral power variations, as a measure of local neuronal ensemble synchronization, as well as phase coherence patterns, as an index of the long-range coordination of these local groups of neurons. Synchronized activity in the gamma band (2040 Hz), previously reported to be related to the engagement of selective attention, showed a clear dissociation of local power and phase coherence between distant regions. In this frequency range, local synchrony characterized the subjects who were focused on word identification and was accompanied by increased coherence in the theta band (48 Hz). Only those subjects who were able to learn the embedded rules showed increased gamma band phase coherence between frontal, temporal, and parietal regions.

Energy-performance tradeoffs in software transactional memory

Transactional memory (TM) is a new synchronization mechanism devised to simplify parallel programming, thereby helping programmers to unleash the power of current multicore processors. Although software implementations of TM (STM) have been extensively analyzed in terms of runtime performance, little attention has been paid to an equally important constraint faced by nearly all computer systems: energy consumption. In this work we conduct a comprehensive study of energy and runtime tradeoff sin software transactional memory systems. We characterize the behavior of three state-of-the-art lock-based STM algorithms, along with three different conflict resolution schemes. As a result of this characterization, we propose a DVFS-based technique that can be integrated into the resolution policies so as to improve the energy-delay product (EDP). Experimental results show that our DVFS-enhanced policies are indeed beneficial for applications with high contention levels. Improvements of up to 59% in EDP can be observed in this scenario, with an average EDP reduction of 16% across the STAMP workloads. © 2012 IEEE.

Parallel Architectures for Many-Core Systems-On-Chip in Deep Sub-Micron Technology

Despite the several issues faced in the past, the evolutionary trend of silicon has kept its constant pace. Today an ever increasing number of cores is integrated onto the same die. Unfortunately, the extraordinary performance achievable by the many-core paradigm is limited by several factors. Memory bandwidth limitation, combined with inefficient synchronization mechanisms, can severely overcome the potential computation capabilities. Moreover, the huge HW/SW design space requires accurate and flexible tools to perform architectural explorations and validation of design choices. In this thesis we focus on the aforementioned aspects: a flexible and accurate Virtual Platform has been developed, targeting a reference many-core architecture. Such tool has been used to perform architectural explorations, focusing on instruction caching architecture and hybrid HW/SW synchronization mechanism. Beside architectural implications, another issue of embedded systems is considered: energy efficiency. Near Threshold Computing is a key research area in the Ultra-Low-Power domain, as it promises a tenfold improvement in energy efficiency compared to super-threshold operation and it mitigates thermal bottlenecks. The physical implications of modern deep sub-micron technology are severely limiting performance and reliability of modern designs. Reliability becomes a major obstacle when operating in NTC, especially memory operation becomes unreliable and can compromise system correctness. In the present work a novel hybrid memory architecture is devised to overcome reliability issues and at the same time improve energy efficiency by means of aggressive voltage scaling when allowed by workload requirements. Variability is another great drawback of near-threshold operation. The greatly increased sensitivity to threshold voltage variations in today a major concern for electronic devices. We introduce a variation-tolerant extension of the baseline many-core architecture. By means of micro-architectural knobs and a lightweight runtime control unit, the baseline architecture becomes dynamically tolerant to variations.

Visualizador de programas Java concurrentes

El presente trabajo fin de grado, que, a partir de ahora, denominaré TFG, consiste en elaborar una monitorización de programas concurrentes en lenguaje Java, para que se visualicen los eventos ocurridos durante la ejecución de los dichos programas. Este trabajo surge en el marco de la asignatura “Concurrencia” de la Escuela Técnica Superior de Ingeniería Informática de la Universidad Politécnica de Madrid, impartida por D. Julio Mariño y D. Ángel Herranz. El objetivo principal de este proyecto es crear una herramienta para el aprendizaje de la asignatura de concurrencia, facilitando la comprensión de los conceptos teóricos, de modo que puedan corregir los posibles errores que haya en sus prácticas. en este proyecto se expone el desarrollo de una librería de visualización de programas concurrentes programados en Java usando un formalismo gráfico similar al empleado en la asignatura. Además esta librería da soporte a los mecanismos de sincronización usados en las prácticas de la asignatura: la librería Monitor (desarrollada por los profesores de la asignatura, D. Ángel Herranz y D. Julio Mariño) y la librería JCSP (Universidad de Kent). ---ABSTRACT---This Bachelor Thesis addresses the problem of monitoring a Java program in order to trace and visualize a certain set of events produced during the execution of concurrent Java programs. This work originates in the subject "Concurrency" of the Computer Science and Engineering degree of our University. The main goal of this work is to have a tool that helps students learning the subject, so they can better understand the core concepts and correct common mistakes in the course practical work. We have implemented a library for visualizing concurrent Java programsusing a graphical notation similar to the one used in class, which supports the design of concurrent programs whose synchronization mechanisms are either monitors(using the Monitor package) or CSP(as implemented in the JCSP library from Kent University).

Mecanismos de sincronia social no ritmo circadiano de atividade durante a coabitação em casais de saguis (Callithrix jacchus)

In marmosets, it was observed that the synchrony among circadian activity profiles of animals that cohabite in family groups is stronger than those of the same sex and age of different families. Inside the group, it is stronger between the younger ones than between them and their parents. However, the mechanisms involved in the social synchrony are unknown. With the aim to investigate the synchronization mechanisms involved in the synchrony between the circadian activity profiles during cohabitation in pairs of marmosets, the motor activity was continuously registered by the use of actmeters on three dyads. The pairs were maintained in two different conditions of illumination: light-dark cycle LD 12:12 (LD cohabitation I – 21 days), and thereafter in LL (~350 lux). Under LL, the pairs were submitted to four experimental situations: 1. Cohabitation (LLJ I – 24 days), 2. Removal of one member of the pair to another room with similar conditions (LLS I – 20 days), 3. Reintroduction of the separated member in the cage of the first situation (LLJ II – 30 days) and 4. Removal of a member from each pair to another experimental room (LLS II – 7 days), to evaluate the mechanisms of synchronization. Ultimately, the members of each pair were reintroduced in the cage and were kept in LD cycle 12:12 (LDJ II – 11 days). The rhythms of pairs free-ran in LL, with identical periods between the members of each pair during the two stages of cohabitation. In the stages in which the animals were separated, only the rhythms of two females free-ran in the first stage and of three animals in the second one. In those conditions, the rhythms of animals of each pair showed different endogenous periods. Besides, during cohabitation in LD and LL, the members of each pair showed a stable phase relationship in the beginning of the active phase, while in the stages in which the animals were separated it was noticed a breaking in the stability in the phase relationships between the circadian activity profiles, with an increase in the difference in the phase angles between them. During cohabitation, at the transition between LD and LL, all animals showed free-running rhythms anticipating progressively the beginning and the end of the active phase in a phase similar to the previous condition, showing signs of entrainment to the previous LD. While in the posterior stages this was observed in only three animals between: LLT I and LLS I, and LLT II and LLS II, evidencing signs of entrainment to social cues between the members of each pair. On the other hand, one animal delayed progressively between LLT I and LLS I, three animals delayed between LLS I and LLT II, and three animals between LLT II and LLS II, perhaps by entrainment to the animals maintained outdoors in the colony. Similar process was observed in four animals between LLS II and LDT II, indicating entrainment to LD. In the transition between LLS I and LLT II, signs of masking was observed in the rhythm of a female in response to the male and in another pair in the rhythm of the male in regard to that of the female. The general and maximum correlations in the circadian activity profiles were stronger during cohabitation in LD and LL than in the absence of social contact in LL, evidencing the social effect. The cohabiting pairs had higher values of the maximum correlation in LD and LL than when the profiles were correlated to animals of different cages, with same or different sexes. Similar results were observed in the general correlation. Therefore, it is suggested that cohabitation induces a strong synchrony between circadian activity profiles in marmosets, which involves entrainment and masking. Nevertheless, additional studies are necessary to evaluate the effect of social cues on the synchronization of the circadian rhythm in pairs of marmosets in the absence of external social cues in order to confirm this hypothesis.

Mechanisms of synchronization and pattern formation in a lattice of pulse-coupled oscillators

We analyze the physical mechanisms leading either to synchronization or to the formation of spatiotemporal patterns in a lattice model of pulse-coupled oscillators. In order to make the system tractable from a mathematical point of view we study a one-dimensional ring with unidirectional coupling. In such a situation, exact results concerning the stability of the fixed of the dynamic evolution of the lattice can be obtained. Furthermore, we show that this stability is the responsible for the different behaviors.

Collision-free beacon scheduling mechanisms for IEEE 802.15.4/Zigbee cluster-tree wireless sensor networks

The recently standardized IEEE 802.15.4/Zigbee protocol stack offers great potentials for ubiquitous and pervasive computing, namely for Wireless Sensor Networks (WSNs). However, there are still some open and ambiguous issues that turn its practical use a challenging task. One of those issues is how to build a synchronized multi-hop cluster-tree network, which is quite suitable for QoS support in WSNs. In fact, the current IEEE 802.15.4/Zigbee specifications restrict the synchronization in the beacon-enabled mode (by the generation of periodic beacon frames) to star-based networks, while it supports multi-hop networking using the peer-to-peer mesh topology, but with no synchronization. Even though both specifications mention the possible use of cluster-tree topologies, which combine multi-hop and synchronization features, the description on how to effectively construct such a network topology is missing. This paper tackles this problem, unveils the ambiguities regarding the use of the cluster-tree topology and proposes two collision-free beacon frame scheduling schemes. We strongly believe that the results provided in this paper trigger a significant step towards the practical and efficient use of IEEE 802.15.4/Zigbee cluster-tree networks.

Synchronization properties of multi-oscillator circadian systems

Dissertation presented to obtain the Ph.D degree in Computational Biology

Sensorimotor synchronization when walking side by side with a point light walker

[Excerpt] Synchronization of periodic movements like side-by-side walking [7] is frequently modeled by coupled oscillators [5] and the coupling strength is defined quantitatively [3]. In contrast, in most studies on sensorimotor synchronization (SMS), simple movements like finger taps are synchronized with simple stimuli like metronomes [4]. While the latter paradigm simplifies matters and allows for the assessment of the relative weights of sensory modalities through systematic variation of the stimuli [1], it might lack ecological validity. Conversely, using more complex movements and stimuli might complicate the specification of mechanisms underlying coupling. We merged the positive aspects of both approaches to study the contribution of auditory and visual information on synchronization during side-by-side walking. As stimuli, we used Point Light Walkers (PLWs) and auralized steps sound; both were constructed from previously captured walking individuals [2][6]. PLWs were retro-projected on a screen and matched according to gender, hip height, and velocity. The participant walked for 7.20m side by side with 1) a PLW, 2) steps sound, or 3) both displayed in temporal congruence. Instruction to participants was to synchronize with the available stimuli. [...]

The neuronal basis of attention: rate versus synchronization modulation

Extensive theoretical and experimental work on the neuronal correlates of visual attention raises two hypotheses about the underlying mechanisms. The first hypothesis, named biased competition, originates from experimental single-cell recordings that have shown that attention upmodulates the firing rates of the neurons encoding the attended features and downregulates the firing rates of the neurons encoding the unattended features. Furthermore, attentional modulation of firing rates increases along the visual pathway. The other, newer hypothesis assigns synchronization a crucial role in the attentional process. It stems from experiments that have shown that attention modulates gamma-frequency synchronization. In this paper, we study the coexistence of the two phenomena using a theoretical framework. We find that the two effects can vary independently of each other and across layers. Therefore, the two phenomena are not concomitant. However, we show that there is an advantage in the processing of information if rate modulation is accompanied by gamma modulation, namely that reaction times are shorter, implying behavioral relevance for gamma synchronization.

Tuning synchronization of integrate-and-fire oscillators through mobility

We analyze the emergence of synchronization in a population of moving integrate-and-fire oscillators. Oscillators, while moving on a plane, interact with their nearest neighbor upon firing time. We discover a nonmonotonic dependence of the synchronization time on the velocity of the agents. Moreover, we find that mechanisms that drive synchronization are different for different dynamical regimes. We report the extreme situation where an interplay between the time scales involved in the dynamical processes completely inhibits the achievement of a coherent state. We also provide estimators for the transitions between the different regimes.

Thread Scheduling Mechanisms for Multiple-Context Parallel Processors

Scheduling tasks to efficiently use the available processor resources is crucial to minimizing the runtime of applications on shared-memory parallel processors. One factor that contributes to poor processor utilization is the idle time caused by long latency operations, such as remote memory references or processor synchronization operations. One way of tolerating this latency is to use a processor with multiple hardware contexts that can rapidly switch to executing another thread of computation whenever a long latency operation occurs, thus increasing processor utilization by overlapping computation with communication. Although multiple contexts are effective for tolerating latency, this effectiveness can be limited by memory and network bandwidth, by cache interference effects among the multiple contexts, and by critical tasks sharing processor resources with less critical tasks. This thesis presents techniques that increase the effectiveness of multiple contexts by intelligently scheduling threads to make more efficient use of processor pipeline, bandwidth, and cache resources. This thesis proposes thread prioritization as a fundamental mechanism for directing the thread schedule on a multiple-context processor. A priority is assigned to each thread either statically or dynamically and is used by the thread scheduler to decide which threads to load in the contexts, and to decide which context to switch to on a context switch. We develop a multiple-context model that integrates both cache and network effects, and shows how thread prioritization can both maintain high processor utilization, and limit increases in critical path runtime caused by multithreading. The model also shows that in order to be effective in bandwidth limited applications, thread prioritization must be extended to prioritize memory requests. We show how simple hardware can prioritize the running of threads in the multiple contexts, and the issuing of requests to both the local memory and the network. Simulation experiments show how thread prioritization is used in a variety of applications. Thread prioritization can improve the performance of synchronization primitives by minimizing the number of processor cycles wasted in spinning and devoting more cycles to critical threads. Thread prioritization can be used in combination with other techniques to improve cache performance and minimize cache interference between different working sets in the cache. For applications that are critical path limited, thread prioritization can improve performance by allowing processor resources to be devoted preferentially to critical threads. These experimental results show that thread prioritization is a mechanism that can be used to implement a wide range of scheduling policies.