Shared resources and precedence constraints with capacity sharing and stealing

This paper proposes a new strategy to integrate shared resources and precedence constraints among real-time tasks, assuming no precise information on critical sections and computation times is available. The concept of bandwidth inheritance is combined with a greedy capacity sharing and stealing policy to efficiently exchange bandwidth among tasks, minimising the degree of deviation from the ideal system's behaviour caused by inter-application blocking. The proposed capacity exchange protocol (CXP) focus on exchanging extra capacities as early, and not necessarily as fairly, as possible. This loss of optimality is worth the reduced complexity as the protocol's behaviour nevertheless tends to be fair in the long run and outperforms other solutions in highly dynamic scenarios, as demonstrated by extensive simulations.

GTS allocation analysis in IEEE 802.15.4 for real-time wireless sensor networks

The IEEE 802.15.4 protocol proposes a flexible communication solution for Low-Rate Wireless Personal Area Networks including sensor networks. It presents the advantage to fit different requirements of potential applications by adequately setting its parameters. When enabling its beacon mode, the protocol makes possible real-time guarantees by using its Guaranteed Time Slot (GTS) mechanism. This paper analyzes the performance of the GTS allocation mechanism in IEEE 802.15.4. The analysis gives a full understanding of the behavior of the GTS mechanism with regards to delay and throughput metrics. First, we propose two accurate models of service curves for a GTS allocation as a function of the IEEE 802.15.4 parameters. We then evaluate the delay bounds guaranteed by an allocation of a GTS using Network Calculus formalism. Finally, based on the analytic results, we analyze the impact of the IEEE 802.15.4 parameters on the throughput and delay bound guaranteed by a GTS allocation. The results of this work pave the way for an efficient dimensioning of an IEEE 802.15.4 cluster.

Fixed Point Decimal Multiplication Using RPS Algorithm

Decimal multiplication is an integral part of financial, commercial, and internet-based computations. A novel design for single digit decimal multiplication that reduces the critical path delay and area for an iterative multiplier is proposed in this research. The partial products are generated using single digit multipliers, and are accumulated based on a novel RPS algorithm. This design uses n single digit multipliers for an n × n multiplication. The latency for the multiplication of two n-digit Binary Coded Decimal (BCD) operands is (n + 1) cycles and a new multiplication can begin every n cycle. The accumulation of final partial products and the first iteration of partial product generation for next set of inputs are done simultaneously. This iterative decimal multiplier offers low latency and high throughput, and can be extended for decimal floating-point multiplication.

Study of ensemble strategies in discovering linear casual models

Determining the causal structure of a domain is frequently a key task in the area of Data Mining and Knowledge Discovery. This paper introduces ensemble learning into linear causal model discovery, then examines several algorithms based on different ensemble strategies including Bagging, Adaboost and GASEN. Experimental results show that (1) Ensemble discovery algorithm can achieve an improved result compared with individual causal discovery algorithm in terms of accuracy; (2) Among all examined ensemble discovery algorithms, BWV algorithm which uses a simple Bagging strategy works excellently compared to other more sophisticated ensemble strategies; (3) Ensemble method can also improve the stability of parameter estimation. In addition, Ensemble discovery algorithm is amenable to parallel and distributed processing, which is important for data mining in large data sets.

Technologies and considerations for developing internet and multiplayer computer games: a tutorial (extended abstract)

Games are universal and probably as old as humankind. Today the development of computer technology, especially the development of fast networks and the Internet, brings games a faster growth than ever before. Game design and development is now a fast-growing entertainment field, with a lot to offer professionally and creatively. In fact, from IT professional’s point of view, creating computer games provides us with all the usual technical challenges associated with software development, such as requirement analysis, architectural design, rapid prototyping, HCI, parallel and distributed processing, code reuse, programming, performance evaluation, testing and maintenance. It also provides challenges on other exciting aspects, such as storyboarding, screenplays, illustration, animation, sound effects, music, and social impact. By developing a computer game from start to finish, one would be able to acquire multi-disciplinary knowledge to become an IT professional for the modern era.

A configurable approach to circuit simulation

This paper presents a configurable architecture which was designed to aid in the simulation of ULSI circuits at the transistor level. Elsewhere [1] this architecture was shown to be able to run such simulations several times as fast as standard circuit simulators such as SPICES. In this paper, after describing the overall idea and the the architecture of the system as a whole, I concentrate on the description of the architecture of the processing elements of the computing array.

4CaaSt: Comprehensive management of Cloud services through a PaaS

The 4CaaSt project aims at developing a PaaS framework that enables flexible definition, marketing, deployment and management of Cloud-based services and applications. The major innovations proposed by 4CaaSt are the blueprint and its management and lifecycle, a one stop shop for Cloud services and the management of resources in the PaaS level (including elasticity). 4CaaSt also provides a portfolio of ready to use Cloud native services and Cloud- aware immigrant technologies.

Hardware Reuse Improvement through the Domain Specific Language dHDL.

The dHDL language has been defined to improve hardware design productivity. This is achieved through the definition of a better reuse interface (including parameters, attributes and macroports) and the creation of control structures that help the designer in the hardware generation process.

Rapid prototyping framework for visual control of autonomous micro aerial vehicles

Rapid prototyping environments can speed up the research of visual control algorithms. We have designed and implemented a software framework for fast prototyping of visual control algorithms for Micro Aerial Vehicles (MAV). We have applied a combination of a proxy-based network communication architecture and a custom Application Programming Interface. This allows multiple experimental configurations, like drone swarms or distributed processing of a drone’s video stream. Currently, the framework supports a low-cost MAV: the Parrot AR.Drone. Real tests have been performed on this platform and the results show comparatively low figures of the extra communication delay introduced by the framework, while adding new functionalities and flexibility to the selected drone. This implementation is open-source and can be downloaded from www.vision4uav.com/?q=VC4MAV-FW

Marco computacional para la definición de un modelo bio-inspirado en la señalización celular

Las Redes de Procesadores Evolutivos-NEP propuestas en [Mitrana et al., 2001], son un modelo computacional bio-inspirado a partir de la evolución de poblaciones de células, definiendo a nivel sintáctico algunas propiedades biológicas. En este modelo, las células están representadas por medio de palabras que describen secuencias de ADN. Informalmente, en algún instante de tiempo, el sistema evolutivo está representado por una colección de palabras cada una de las cuales representa una célula. El espacio genotipo de las especies, es un conjunto que recoge aquellas palabras que son aceptadas como sobrevivientes (es decir, como \correctas"). Desde el punto de vista de la evolución, las células pertenecen a especies y su comunidad evoluciona de acuerdo a procesos biológicos como la mutación y la división celular. éstos procesos representan el proceso natural de evolución y ponen de manifiesto una característica intrínseca de la naturaleza: el paralelismo. En este modelo, estos procesos son vistos como operaciones sobre palabras. Formalmente, el modelo de las NEP constituyen una arquitectura paralela y distribuida de procesamiento simbólico inspirada en la Máquina de conexión [Hillis, 1981], en el Paradigma de Flujo Lógico [Errico and Jesshope, 1994] y en las Redes de Procesadores Paralelos de Lenguajes (RPPL) [Csuhaj-Varju and Salomaa, 1997]. Al modelo NEP se han ido agregando nuevas y novedosas extensiones hasta el punto que actualmente podemos hablar de una familia de Redes de Procesadores Bio-inspirados (NBP) [Mitrana et al., 2012b]. Un considerable número de trabajos a lo largo de los últimos años han demostrado la potencia computacional de la familia NBP. En general, éstos modelos son computacionalmente completos, universales y eficientes [Manea et al., 2007], [Manea et al., 2010b], [Mitrana and Martín-Vide, 2005]. De acuerdo a lo anterior, se puede afirmar que el modelo NEP ha adquirido hasta el momento un nivel de madurez considerable. Sin embargo, aunque el modelo es de inspiración biológica, sus metas siguen estando motivadas en la Teoría de Lenguajes Formales y las Ciencias de la Computación. En este sentido, los aspectos biológicos han sido abordados desde una perspectiva cualitativa y el acercamiento a la realidad biológica es de forma meramente sintáctica. Para considerar estos aspectos y lograr dicho acercamiento es necesario que el modelo NEP tenga una perspectiva más amplia que incorpore la interacción de aspectos tanto cualitativos como cuantitativos. La contribución de esta Tesis puede considerarse como un paso hacia adelante en una nueva etapa de los NEPs, donde el carácter cuantitativo del modelo es de primordial interés y donde existen posibilidades de un cambio visible en el enfoque de interés del dominio de los problemas a considerar: de las ciencias de la computación hacia la simulación/modelado biológico y viceversa, entre otros. El marco computacional que proponemos en esta Tesis extiende el modelo de las Redes de Procesadores Evolutivos (NEP) y define arquitectura inspirada en la definición de bloques funcionales del proceso de señalización celular para la solución de problemas computacionales complejos y el modelado de fenómenos celulares desde una perspectiva discreta. En particular, se proponen dos extensiones: (1) los Transductores basados en Redes de Procesadores Evolutivos (NEPT), y (2) las Redes Parametrizadas de Procesadores Evolutivos Polarizados (PNPEP). La conservación de las propiedades y el poder computacional tanto de NEPT como de PNPEP se demuestra formalmente. Varias simulaciones de procesos relacionados con la señalización celular son abordadas sintáctica y computacionalmente, con el _n de mostrar la aplicabilidad e idoneidad de estas dos extensiones. ABSTRACT Network of Evolutionary Processors -NEP was proposed in [Mitrana et al., 2001], as a computational model inspired by the evolution of cell populations, which might model some properties of evolving cell communities at the syntactical level. In this model, cells are represented by words which encode their DNA sequences. Informally, at any moment of time, the evolutionary system is described by a collection of words, where each word represents one cell. Cells belong to species and their community evolves according to mutations and division which are defined by operations on words. Only those cells accepted as survivors (correct) are represented by a word in a given set of words, called the genotype space of the species. This feature is analogous with the natural process of evolution. Formally, NEP is based on an architecture for parallel and distributed processing inspired from the Connection Machine [Hillis, 1981], the Flow Logic Paradigm [Errico and Jesshope, 1994] and the Networks of Parallel Language Processors (RPPL) [Csuhaj-Varju and Salomaa, 1997]. Since the date when NEP was proposed, several extensions and variants have appeared engendering a new set of models named Networks of Bio-inspired Processors (NBP) [Mitrana et al., 2012b]. During this time, several works have proved the computational power of NBP. Specifically, their efficiency, universality, and computational completeness have been thoroughly investigated [Manea et al., 2007, Manea et al., 2010b, Mitrana and Martín-Vide, 2005]. Therefore, we can say that the NEP model has reached its maturity. Nevertheless, although the NEP model is biologically inspired, this model is mainly motivated by mathematical and computer science goals. In this context, the biological aspects are only considered from a qualitative and syntactical perspective. In view of this lack, it is important to try to keep the NEP theory as close as possible to the biological reality, extending their perspective incorporating the interplay of qualitative and quantitative aspects. The contribution of this Thesis, can be considered as a starting point in a new era of the NEP model. Then, the quantitative character of the NEP model is mandatory and it can address completely new different types of problems with respect to the classical computational domain (e.g. from the computer science to system biology). Therefore, the computational framework that we propose extends the NEP model and defines an architecture inspired by the functional blocks from cellular signaling in order to solve complex computational problems and cellular phenomena modeled from a discrete perspective. Particularly, we propose two extensions, namely: (1) Transducers based on Network of Evolutionary Processors (NEPT), and (2) Parametrized Network of Polarized Evolutionary Processors (PNPEP). Additionally, we have formally proved that the properties and computational power of NEP is kept in both extensions. Several simulations about processes related with cellular signaling both syntactical and computationally have been considered to show the model suitability.

Computer aided parallelisation of unstructured mesh codes

Abstract not available

Issues and strategies in the parallelisation of unstructured multiphysics code

Unstructured mesh based codes for the modelling of continuum physics phenomena have evolved to provide the facility to model complex interacting systems. Such codes have the potential to provide a high performance on parallel platforms for a small investment in programming. The critical parameters for success are to minimise changes to the code to allow for maintenance while providing high parallel efficiency, scalability to large numbers of processors and portability to a wide range of platforms. The paradigm of domain decomposition with message passing has for some time been demonstrated to provide a high level of efficiency, scalability and portability across shared and distributed memory systems without the need to re-author the code into a new language. This paper addresses these issues in the parallelisation of a complex three dimensional unstructured mesh Finite Volume multiphysics code and discusses the implications of automating the parallelisation process.

Software tools for automating the parallelisation of FORTRAN computational mechanics codes

It is now clear that the concept of a HPC compiler which automatically produces highly efficient parallel implementations is a pipe-dream. Another route is to recognise from the outset that user information is required and to develop tools that embed user interaction in the transformation of code from scalar to parallel form, and then use conventional compilers with a set of communication calls. This represents the key idea underlying the development of the CAPTools software environment. The initial version of CAPTools is focused upon single block structured mesh computational mechanics codes. The capability for unstructured mesh codes is under test now and block structured meshes will be included next. The parallelisation process can be completed rapidly for modest codes and the parallel performance approaches that which is delivered by hand parallelisations.

StreamCloud: An Elastic Parallel-Distributed Stream Processing Engine

In recent years, applications in domains such as telecommunications, network security or large scale sensor networks showed the limits of the traditional store-then-process paradigm. In this context, Stream Processing Engines emerged as a candidate solution for all these applications demanding for high processing capacity with low processing latency guarantees. With Stream Processing Engines, data streams are not persisted but rather processed on the fly, producing results continuously. Current Stream Processing Engines, either centralized or distributed, do not scale with the input load due to single-node bottlenecks. Moreover, they are based on static configurations that lead to either under or over-provisioning. This Ph.D. thesis discusses StreamCloud, an elastic paralleldistributed stream processing engine that enables for processing of large data stream volumes. Stream- Cloud minimizes the distribution and parallelization overhead introducing novel techniques that split queries into parallel subqueries and allocate them to independent sets of nodes. Moreover, Stream- Cloud elastic and dynamic load balancing protocols enable for effective adjustment of resources depending on the incoming load. Together with the parallelization and elasticity techniques, Stream- Cloud defines a novel fault tolerance protocol that introduces minimal overhead while providing fast recovery. StreamCloud has been fully implemented and evaluated using several real word applications such as fraud detection applications or network analysis applications. The evaluation, conducted using a cluster with more than 300 cores, demonstrates the large scalability, the elasticity and fault tolerance effectiveness of StreamCloud. Resumen En los útimos años, aplicaciones en dominios tales como telecomunicaciones, seguridad de redes y redes de sensores de gran escala se han encontrado con múltiples limitaciones en el paradigma tradicional de bases de datos. En este contexto, los sistemas de procesamiento de flujos de datos han emergido como solución a estas aplicaciones que demandan una alta capacidad de procesamiento con una baja latencia. En los sistemas de procesamiento de flujos de datos, los datos no se persisten y luego se procesan, en su lugar los datos son procesados al vuelo en memoria produciendo resultados de forma continua. Los actuales sistemas de procesamiento de flujos de datos, tanto los centralizados, como los distribuidos, no escalan respecto a la carga de entrada del sistema debido a un cuello de botella producido por la concentración de flujos de datos completos en nodos individuales. Por otra parte, éstos están basados en configuraciones estáticas lo que conducen a un sobre o bajo aprovisionamiento. Esta tesis doctoral presenta StreamCloud, un sistema elástico paralelo-distribuido para el procesamiento de flujos de datos que es capaz de procesar grandes volúmenes de datos. StreamCloud minimiza el coste de distribución y paralelización por medio de una técnica novedosa la cual particiona las queries en subqueries paralelas repartiéndolas en subconjuntos de nodos independientes. Ademas, Stream- Cloud posee protocolos de elasticidad y equilibrado de carga que permiten una optimización de los recursos dependiendo de la carga del sistema. Unidos a los protocolos de paralelización y elasticidad, StreamCloud define un protocolo de tolerancia a fallos que introduce un coste mínimo mientras que proporciona una rápida recuperación. StreamCloud ha sido implementado y evaluado mediante varias aplicaciones del mundo real tales como aplicaciones de detección de fraude o aplicaciones de análisis del tráfico de red. La evaluación ha sido realizada en un cluster con más de 300 núcleos, demostrando la alta escalabilidad y la efectividad tanto de la elasticidad, como de la tolerancia a fallos de StreamCloud.