Tesis por compendio / [EN] Over the last years, multiagent systems have been proven to be a powerful and versatile paradigm, with a big potential when it comes to solving complex problems in dynamic and distributed environments, due to their flexible and adaptive behavior. This potential does not only come from the individual features of agents (such as autonomy, reactivity or reasoning power), but also to their capability to communicate, cooperate and coordinate in order to fulfill their goals. In fact, it is this social behavior what makes multiagent systems so powerful, much more than the individual capabilities of agents. The social behavior of multiagent systems is usually developed by means of high level abstractions, protocols and languages, which normally rely on (or at least, benefit from) agents being able to communicate and interact indirectly. However, in the development process, such high level concepts habitually become weakly supported, with mechanisms such as traditional messaging, massive broadcasting, blackboard systems or ad hoc solutions. This lack of an appropriate way to support indirect communication in actual multiagent systems compromises their potential. This PhD thesis proposes the use of event tracing as a flexible, effective and efficient support for indirect interaction and communication in multiagent systems. The main contribution of this thesis is TRAMMAS, a generic, abstract model for event tracing support in multiagent systems. The model allows all entities in the system to share their information as trace events, so that any other entity which require this information is able to receive it. Along with the model, the thesis also presents an abstract architecture, which redefines the model in terms of a set of tracing facilities that can be then easily incorporated to an actual multiagent platform. This architecture follows a service-oriented approach, so that the tracing facilities are provided in the same way than other traditional services offered by the platform. In this way, event tracing can be considered as an additional information provider for entities in the multiagent system, and as such, it can be integrated from the earliest stages of the development process. / [ES] A lo largo de los últimos años, los sistemas multiagente han demostrado ser un paradigma potente y versátil, con un gran potencial a la hora de resolver problemas complejos en entornos dinámicos y distribuidos, gracias a su comportamiento flexible y adaptativo. Este potencial no es debido únicamente a las características individuales de los agentes (como son su autonomía, y su capacidades de reacción y de razonamiento), sino que también se debe a su capacidad de comunicación y cooperación a la hora de conseguir sus objetivos. De hecho, por encima de la capacidad individual de los agentes, es este comportamiento social el que dota de potencial a los sistemas multiagente. El comportamiento social de los sistemas multiagente suele desarrollarse empleando abstracciones, protocolos y lenguajes de alto nivel, los cuales, a su vez, se basan normalmente en la capacidad para comunicarse e interactuar de manera indirecta de los agentes (o como mínimo, se benefician en gran medida de dicha capacidad). Sin embargo, en el proceso de desarrollo software, estos conceptos de alto nivel son soportados habitualmente de manera débil, mediante mecanismos como la mensajería tradicional, la difusión masiva, o el uso de pizarras, o mediante soluciones totalmente ad hoc. Esta carencia de un soporte genérico y apropiado para la comunicación indirecta en los sistemas multiagente reales compromete su potencial. Esta tesis doctoral propone el uso del trazado de eventos como un soporte flexible, efectivo y eficiente para la comunicación indirecta en sistemas multiagente. La principal contribución de esta tesis es TRAMMAS, un modelo genérico y abstracto para dar soporte al trazado de eventos en sistemas multiagente. El modelo permite a cualquier entidad del sistema compartir su información en forma de eventos de traza, de tal manera que cualquier otra entidad que requiera esta información sea capaz de recibirla. Junto con el modelo, la tesis también presenta una arquitectura {abs}{trac}{ta}, que redefine el modelo como un conjunto de funcionalidades que pueden ser fácilmente incorporadas a una plataforma multiagente real. Esta arquitectura sigue un enfoque orientado a servicios, de modo que las funcionalidades de traza son ofrecidas por parte de la plataforma de manera similar a los servicios tradicionales. De esta forma, el trazado de eventos puede ser considerado como una fuente adicional de información para las entidades del sistema multiagente y, como tal, puede integrarse en el proceso de desarrollo software desde sus primeras etapas. / [CA] Al llarg dels últims anys, els sistemes multiagent han demostrat ser un paradigma potent i versàtil, amb un gran potencial a l'hora de resoldre problemes complexes a entorns dinàmics i distribuïts, gràcies al seu comportament flexible i adaptatiu. Aquest potencial no és només degut a les característiques individuals dels agents (com són la seua autonomia, i les capacitats de reacció i raonament), sinó també a la seua capacitat de comunicació i cooperació a l'hora d'aconseguir els seus objectius. De fet, per damunt de la capacitat individual dels agents, es aquest comportament social el que dóna potencial als sistemes multiagent. El comportament social dels sistemes multiagent solen desenvolupar-se utilitzant abstraccions, protocols i llenguatges d'alt nivell, els quals, al seu torn, es basen normalment a la capacitat dels agents de comunicar-se i interactuar de manera indirecta (o com a mínim, es beneficien en gran mesura d'aquesta capacitat). Tanmateix, al procés de desenvolupament software, aquests conceptes d'alt nivell son suportats habitualment d'una manera dèbil, mitjançant mecanismes com la missatgeria tradicional, la difusió massiva o l'ús de pissarres, o mitjançant solucions totalment ad hoc. Aquesta carència d'un suport genèric i apropiat per a la comunicació indirecta als sistemes multiagent reals compromet el seu potencial. Aquesta tesi doctoral proposa l'ús del traçat d'esdeveniments com un suport flexible, efectiu i eficient per a la comunicació indirecta a sistemes multiagent. La principal contribució d'aquesta tesi és TRAMMAS, un model genèric i abstracte per a donar suport al traçat d'esdeveniments a sistemes multiagent. El model permet a qualsevol entitat del sistema compartir la seua informació amb la forma d'esdeveniments de traça, de tal forma que qualsevol altra entitat que necessite aquesta informació siga capaç de rebre-la. Junt amb el model, la tesi també presenta una arquitectura abstracta, que redefineix el model com un conjunt de funcionalitats que poden ser fàcilment incorporades a una plataforma multiagent real. Aquesta arquitectura segueix un enfoc orientat a serveis, de manera que les funcionalitats de traça són oferides per part de la plataforma de manera similar als serveis tradicionals. D'aquesta manera, el traçat d'esdeveniments pot ser considerat com una font addicional d'informació per a les entitats del sistema multiagent, i com a tal, pot integrar-se al procés de desenvolupament software des de les seues primeres etapes. / Búrdalo Rapa, LA. (2016). TRAMMAS: Enhancing Communication in Multiagent Systems [Tesis doctoral]. Universitat Politècnica de València. https://doi.org/10.4995/Thesis/10251/61765 / Compendio

The thesis presents a contribution to the analysis and visualization of computational performance based on event traces with a particular focus on parallel programs and High Performance Computing (HPC). Event traces contain detailed information about specified incidents (events) during run-time of programs and allow minute investigation of dynamic program behavior, various performance metrics, and possible causes of performance flaws. Due to long running and highly parallel programs and very fine detail resolutions, event traces can accumulate huge amounts of data which become a challenge for interactive as well as automatic analysis and visualization tools. The thesis proposes a method of exploiting redundancy in the event traces in order to reduce the memory requirements and the computational complexity of event trace analysis. The sources of redundancy are repeated segments of the original program, either through iterative or recursive algorithms or through SPMD-style parallel programs, which produce equal or similar repeated event sequences. The data reduction technique is based on the novel Complete Call Graph (CCG) data structure which allows domain specific data compression for event traces in a combination of lossless and lossy methods. All deviations due to lossy data compression can be controlled by constant bounds. The compression of the CCG data structure is incorporated in the construction process, such that at no point substantial uncompressed parts have to be stored. Experiments with real-world example traces reveal the potential for very high data compression. The results range from factors of 3 to 15 for small scale compression with minimum deviation of the data to factors > 100 for large scale compression with moderate deviation. Based on the CCG data structure, new algorithms for the most common evaluation and analysis methods for event traces are presented, which require no explicit decompression. By avoiding repeated evaluation of formerly redundant event sequences, the computational effort of the new algorithms can be reduced in the same extent as memory consumption. The thesis includes a comprehensive discussion of the state-of-the-art and related work, a detailed presentation of the design of the CCG data structure, an elaborate description of algorithms for construction, compression, and analysis of CCGs, and an extensive experimental validation of all components. / Diese Dissertation stellt einen neuartigen Ansatz für die Analyse und Visualisierung der Berechnungs-Performance vor, der auf dem Ereignis-Tracing basiert und insbesondere auf parallele Programme und das Hochleistungsrechnen (High Performance Computing, HPC) zugeschnitten ist. Ereignis-Traces (Ereignis-Spuren) enthalten detaillierte Informationen über spezifizierte Ereignisse während der Laufzeit eines Programms und erlauben eine sehr genaue Untersuchung des dynamischen Verhaltens, verschiedener Performance-Metriken und potentieller Performance-Probleme. Aufgrund lang laufender und hoch paralleler Anwendungen und dem hohen Detailgrad kann das Ereignis-Tracing sehr große Datenmengen produzieren. Diese stellen ihrerseits eine Herausforderung für interaktive und automatische Analyse- und Visualisierungswerkzeuge dar. Die vorliegende Arbeit präsentiert eine Methode, die Redundanzen in den Ereignis-Traces ausnutzt, um sowohl die Speicheranforderungen als auch die Laufzeitkomplexität der Trace-Analyse zu reduzieren. Die Ursachen für Redundanzen sind wiederholt ausgeführte Programmabschnitte, entweder durch iterative oder rekursive Algorithmen oder durch SPMD-Parallelisierung, die gleiche oder ähnliche Ereignis-Sequenzen erzeugen. Die Datenreduktion basiert auf der neuartigen Datenstruktur der "Vollständigen Aufruf-Graphen" (Complete Call Graph, CCG) und erlaubt eine Kombination von verlustfreier und verlustbehafteter Datenkompression. Dabei können konstante Grenzen für alle Abweichungen durch verlustbehaftete Kompression vorgegeben werden. Die Datenkompression ist in den Aufbau der Datenstruktur integriert, so dass keine umfangreichen unkomprimierten Teile vor der Kompression im Hauptspeicher gehalten werden müssen. Das enorme Kompressionsvermögen des neuen Ansatzes wird anhand einer Reihe von Beispielen aus realen Anwendungsszenarien nachgewiesen. Die dabei erzielten Resultate reichen von Kompressionsfaktoren von 3 bis 5 mit nur minimalen Abweichungen aufgrund der verlustbehafteten Kompression bis zu Faktoren > 100 für hochgradige Kompression. Basierend auf der CCG_Datenstruktur werden außerdem neue Auswertungs- und Analyseverfahren für Ereignis-Traces vorgestellt, die ohne explizite Dekompression auskommen. Damit kann die Laufzeitkomplexität der Analyse im selben Maß gesenkt werden wie der Hauptspeicherbedarf, indem komprimierte Ereignis-Sequenzen nicht mehrmals analysiert werden. Die vorliegende Dissertation enthält eine ausführliche Vorstellung des Stands der Technik und verwandter Arbeiten in diesem Bereich, eine detaillierte Herleitung der neu eingeführten Daten-strukturen, der Konstruktions-, Kompressions- und Analysealgorithmen sowie eine umfangreiche experimentelle Auswertung und Validierung aller Bestandteile.

This thesis contributes to the field of performance analysis in High Performance Computing with new concepts for in-memory event tracing. Event tracing records runtime events of an application and stores each with a precise time stamp and further relevant metrics. The high resolution and detailed information allows an in-depth analysis of the dynamic program behavior, interactions in parallel applications, and potential performance issues. For long-running and large-scale parallel applications, event-based tracing faces three challenges, yet unsolved: the number of resulting trace files limits scalability, the huge amounts of collected data overwhelm file systems and analysis capabilities, and the measurement bias, in particular, due to intermediate memory buffer flushes prevents a correct analysis. This thesis proposes concepts for an in-memory event tracing workflow. These concepts include new enhanced encoding techniques to increase memory efficiency and novel strategies for runtime event reduction to dynamically adapt trace size during runtime. An in-memory event tracing workflow based on these concepts meets all three challenges: First, it not only overcomes the scalability limitations due to the number of resulting trace files but eliminates the overhead of file system interaction altogether. Second, the enhanced encoding techniques and event reduction lead to remarkable smaller trace sizes. Finally, an in-memory event tracing workflow completely avoids intermediate memory buffer flushes, which minimizes measurement bias and allows a meaningful performance analysis. The concepts further include the Hierarchical Memory Buffer data structure, which incorporates a multi-dimensional, hierarchical ordering of events by common metrics, such as time stamp, calling context, event class, and function call duration. This hierarchical ordering allows a low-overhead event encoding, event reduction and event filtering, as well as new hierarchy-aided analysis requests. An experimental evaluation based on real-life applications and a detailed case study underline the capabilities of the concepts presented in this thesis. The new enhanced encoding techniques reduce memory allocation during runtime by a factor of 3.3 to 7.2, while at the same do not introduce any additional overhead. Furthermore, the combined concepts including the enhanced encoding techniques, event reduction, and a new filter based on function duration within the Hierarchical Memory Buffer remarkably reduce the resulting trace size up to three orders of magnitude and keep an entire measurement within a single fixed-size memory buffer, while still providing a coarse but meaningful analysis of the application. This thesis includes a discussion of the state-of-the-art and related work, a detailed presentation of the enhanced encoding techniques, the event reduction strategies, the Hierarchical Memory Buffer data structure, and a extensive experimental evaluation of all concepts.

The thesis presents a contribution to the analysis and visualization of computational performance based on event traces with a particular focus on parallel programs and High Performance Computing (HPC). Event traces contain detailed information about specified incidents (events) during run-time of programs and allow minute investigation of dynamic program behavior, various performance metrics, and possible causes of performance flaws. Due to long running and highly parallel programs and very fine detail resolutions, event traces can accumulate huge amounts of data which become a challenge for interactive as well as automatic analysis and visualization tools. The thesis proposes a method of exploiting redundancy in the event traces in order to reduce the memory requirements and the computational complexity of event trace analysis. The sources of redundancy are repeated segments of the original program, either through iterative or recursive algorithms or through SPMD-style parallel programs, which produce equal or similar repeated event sequences. The data reduction technique is based on the novel Complete Call Graph (CCG) data structure which allows domain specific data compression for event traces in a combination of lossless and lossy methods. All deviations due to lossy data compression can be controlled by constant bounds. The compression of the CCG data structure is incorporated in the construction process, such that at no point substantial uncompressed parts have to be stored. Experiments with real-world example traces reveal the potential for very high data compression. The results range from factors of 3 to 15 for small scale compression with minimum deviation of the data to factors > 100 for large scale compression with moderate deviation. Based on the CCG data structure, new algorithms for the most common evaluation and analysis methods for event traces are presented, which require no explicit decompression. By avoiding repeated evaluation of formerly redundant event sequences, the computational effort of the new algorithms can be reduced in the same extent as memory consumption. The thesis includes a comprehensive discussion of the state-of-the-art and related work, a detailed presentation of the design of the CCG data structure, an elaborate description of algorithms for construction, compression, and analysis of CCGs, and an extensive experimental validation of all components. / Diese Dissertation stellt einen neuartigen Ansatz für die Analyse und Visualisierung der Berechnungs-Performance vor, der auf dem Ereignis-Tracing basiert und insbesondere auf parallele Programme und das Hochleistungsrechnen (High Performance Computing, HPC) zugeschnitten ist. Ereignis-Traces (Ereignis-Spuren) enthalten detaillierte Informationen über spezifizierte Ereignisse während der Laufzeit eines Programms und erlauben eine sehr genaue Untersuchung des dynamischen Verhaltens, verschiedener Performance-Metriken und potentieller Performance-Probleme. Aufgrund lang laufender und hoch paralleler Anwendungen und dem hohen Detailgrad kann das Ereignis-Tracing sehr große Datenmengen produzieren. Diese stellen ihrerseits eine Herausforderung für interaktive und automatische Analyse- und Visualisierungswerkzeuge dar. Die vorliegende Arbeit präsentiert eine Methode, die Redundanzen in den Ereignis-Traces ausnutzt, um sowohl die Speicheranforderungen als auch die Laufzeitkomplexität der Trace-Analyse zu reduzieren. Die Ursachen für Redundanzen sind wiederholt ausgeführte Programmabschnitte, entweder durch iterative oder rekursive Algorithmen oder durch SPMD-Parallelisierung, die gleiche oder ähnliche Ereignis-Sequenzen erzeugen. Die Datenreduktion basiert auf der neuartigen Datenstruktur der "Vollständigen Aufruf-Graphen" (Complete Call Graph, CCG) und erlaubt eine Kombination von verlustfreier und verlustbehafteter Datenkompression. Dabei können konstante Grenzen für alle Abweichungen durch verlustbehaftete Kompression vorgegeben werden. Die Datenkompression ist in den Aufbau der Datenstruktur integriert, so dass keine umfangreichen unkomprimierten Teile vor der Kompression im Hauptspeicher gehalten werden müssen. Das enorme Kompressionsvermögen des neuen Ansatzes wird anhand einer Reihe von Beispielen aus realen Anwendungsszenarien nachgewiesen. Die dabei erzielten Resultate reichen von Kompressionsfaktoren von 3 bis 5 mit nur minimalen Abweichungen aufgrund der verlustbehafteten Kompression bis zu Faktoren > 100 für hochgradige Kompression. Basierend auf der CCG_Datenstruktur werden außerdem neue Auswertungs- und Analyseverfahren für Ereignis-Traces vorgestellt, die ohne explizite Dekompression auskommen. Damit kann die Laufzeitkomplexität der Analyse im selben Maß gesenkt werden wie der Hauptspeicherbedarf, indem komprimierte Ereignis-Sequenzen nicht mehrmals analysiert werden. Die vorliegende Dissertation enthält eine ausführliche Vorstellung des Stands der Technik und verwandter Arbeiten in diesem Bereich, eine detaillierte Herleitung der neu eingeführten Daten-strukturen, der Konstruktions-, Kompressions- und Analysealgorithmen sowie eine umfangreiche experimentelle Auswertung und Validierung aller Bestandteile.

À l'heure actuelle, les dispositifs embarqués regroupent une grande variété d'applications, ayant des fonctionnalités complexes et demandant une puissance de calcul de plus en plus importante. Ils évoluent actuellement de systèmes multiprocesseur sur puce vers des architectures many-core et posent de nouveaux défis au développement de logiciel embarqué. En effet, Il a classiquement été guidé par les performances et donc par les besoins spécifiques des plates-formes. Or, cette approche s'avère trop couteuse avec les nouvelles architectures matérielles et leurs évolutions rapprochées. Actuellement, il n'y a pas un consensus sur les environnements à utiliser pour programmer les nouvelles architectures embarquées. Afin de permettre une programmation plus rapide du logiciel embarqué, la chaîne de développement a besoin d'outils pour la mise au point des applications. Cette mise au point s'appuie sur des techniques d'observation, qui consistent à recueillir des informations sur le comportement du système embarqué pendant l'exécution. Les techniques d'observation actuelles ne supportent qu'un nombre limité de processeurs et sont fortement dépendantes des caractéristiques matérielles. Dans cette thèse, nous proposons EMBera~: une approche à base de composants pour l'observation de systèmes multiprocesseurs sur puce. EMBera vise la généricité, la portabilité, l'observation d'un grand nombre d'éléments, ainsi que le contrôle de l'intrusion. La généricité est obtenue par l'encapsulation de fonctionnalités spécifiques et l'exportation d'interfaces génériques d'observation. La portabilité est possible grâce à des composants qui, d'une part, ciblent des traitements communs aux MPSoCs, et d'autre part, permettent d'être adaptés aux spécificités des plates-formes. Le passage à l'échelle est réussi en permettant une observation partielle d'un système en se concentrant uniquement sur les éléments d'intérêt~: les modules applicatifs, les composants matériels ou les différents niveaux de la pile logicielle. Le contrôle de l'intrusion est facilité par la possibilité de configurer le type et le niveau de détail des mécanismes de collecte de données. L'approche est validée par le biais de différentes études de cas qui utilisent plusieurs configurations matérielles et logicielles. Nous montrons que cette approche offre une vraie valeur ajoutée dans le support du développement de logiciels embarqués. / Embedded software development faces new challenges as embedded devices evolve from Multiprocessor Systems on Chip (MPSoC) with heterogeneous CPU towards many-core architectures. The classical approach of optimizing embedded software in a platform-specific way is no longer applicable as it is too costly. Moreover, there is no consensus on the programming environments to be used for the new and rapidly changing embedded architectures. MPSoC software development needs debugging tools. These tools are based on observation techniques whose role is to gather information about the embedded system execution. Current techniques support only a limited number of processors and are highly dependent on hardware characteristics. In this thesis, we propose EMBera, a component-based approach to MPSoC observation. EMBera aims at providing genericity, portability, scalability and intrusion control. Genericity is obtained by encapsulating specific embedded features and exporting generic observation interfaces. Portability is achieved through components targeting common treatments for MPSoCs but allowing specialization. Scalability is achieved by observing only the elements of interest from the system, namely application modules, hardware components or the different levels of the software stack. Intrusion control is facilitated by the possibility to configure the type and the level of detail of data collection mechanisms. The EMBera approach is validated by different case studies using different hardware and software configurations. We show that our approach provides a real added value in supporting the embedded software development.

This thesis contributes to the field of performance analysis in High Performance Computing with new concepts for in-memory event tracing. Event tracing records runtime events of an application and stores each with a precise time stamp and further relevant metrics. The high resolution and detailed information allows an in-depth analysis of the dynamic program behavior, interactions in parallel applications, and potential performance issues. For long-running and large-scale parallel applications, event-based tracing faces three challenges, yet unsolved: the number of resulting trace files limits scalability, the huge amounts of collected data overwhelm file systems and analysis capabilities, and the measurement bias, in particular, due to intermediate memory buffer flushes prevents a correct analysis. This thesis proposes concepts for an in-memory event tracing workflow. These concepts include new enhanced encoding techniques to increase memory efficiency and novel strategies for runtime event reduction to dynamically adapt trace size during runtime. An in-memory event tracing workflow based on these concepts meets all three challenges: First, it not only overcomes the scalability limitations due to the number of resulting trace files but eliminates the overhead of file system interaction altogether. Second, the enhanced encoding techniques and event reduction lead to remarkable smaller trace sizes. Finally, an in-memory event tracing workflow completely avoids intermediate memory buffer flushes, which minimizes measurement bias and allows a meaningful performance analysis. The concepts further include the Hierarchical Memory Buffer data structure, which incorporates a multi-dimensional, hierarchical ordering of events by common metrics, such as time stamp, calling context, event class, and function call duration. This hierarchical ordering allows a low-overhead event encoding, event reduction and event filtering, as well as new hierarchy-aided analysis requests. An experimental evaluation based on real-life applications and a detailed case study underline the capabilities of the concepts presented in this thesis. The new enhanced encoding techniques reduce memory allocation during runtime by a factor of 3.3 to 7.2, while at the same do not introduce any additional overhead. Furthermore, the combined concepts including the enhanced encoding techniques, event reduction, and a new filter based on function duration within the Hierarchical Memory Buffer remarkably reduce the resulting trace size up to three orders of magnitude and keep an entire measurement within a single fixed-size memory buffer, while still providing a coarse but meaningful analysis of the application. This thesis includes a discussion of the state-of-the-art and related work, a detailed presentation of the enhanced encoding techniques, the event reduction strategies, the Hierarchical Memory Buffer data structure, and a extensive experimental evaluation of all concepts.