{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"institution":[{"id":[{"id":"https:\/\/ror.org\/03mb6wj31","id-type":"ROR","asserted-by":"publisher"},{"id":"https:\/\/www.isni.org\/000000041937028X","id-type":"ISNI","asserted-by":"publisher"},{"id":"https:\/\/www.wikidata.org\/entity\/Q1640731","id-type":"wikidata","asserted-by":"publisher"}],"name":"Universitat Polit\u00e8cnica de Catalunya","acronym":["UPC"]}],"indexed":{"date-parts":[[2026,7,30]],"date-time":"2026-07-30T14:41:39Z","timestamp":1785422499371,"version":"3.56.0"},"reference-count":0,"publisher":"Universitat Polit\u00e8cnica de Catalunya","license":[{"content-version":"vor","delay-in-days":0,"URL":"http:\/\/creativecommons.org\/licenses\/by-nc-nd\/3.0\/es\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"abstract":"<jats:p>With the recent switch in the design of general purpose processors from frequency scaling of a single processor core towards increasing the number of processor cores, parallel programming became important not only for scientific programming but also for general purpose programming. This also stressed the importance of programmability of existing parallel programming models which were primarily designed for performance. It was soon recognized that new programming models are needed that will make parallel programming possible not only to experts, but to a general programming community.\r\nTransactional Memory (TM) is an example which follows this premise. It improves dramatically over any previous synchronization mechanism in terms of programmability and composability, at the price of possibly reduced performance. The main source of performance degradation in Transactional Memory is the overhead of transactional execution. Our work on parallelizing Quake game engine is a clear example of this problem. We show that Software Transactional Memory is superior in terms of programmability compared to lock based programming, but that performance is hindered due to extreme amount of overhead introduced by transactional execution.\r\nIn the meantime, a significant research effort has been invested in overcoming this problem. Our approach is aimed towards improving the performance of transactional code by reducing transactional data conflicts. The idea is based on the organization of the code in which highly conflicting data is promoted to dataflow tokens that coordinate the execution of transactions.\r\nThe main contribution of this thesis is Atomic Dataflow model (ADF), a new task-based parallel programming model for C\/C++ that integrates dataflow abstractions into the shared memory programming model. The ADF model provides language constructs that allow a programmer to delineate a program into a set of tasks and to explicitly define data dependencies for each task. The task dependency information is conveyed to the ADF runtime system that constructs a dataflow task graph that governs the execution of a program. Additionally, the ADF model allows tasks to share data. The key idea is that computation is triggered by dataflow between tasks but that, within a task, execution occurs by making atomic updates to common mutable state. To that end, the ADF model employs transactional memory, which guarantees atomicity of shared memory updates.\r\nThe second contribution of this thesis is DaSH - the first comprehensive benchmark suite for hybrid dataflow and shared memory programming models. DaSH features 11 benchmarks, each representing one of the Berkeley dwarfs that capture patterns of communication and computation common to a wide range of emerging applications. DaSH includes sequential and shared-memory implementations based on OpenMP and TBB to facilitate easy comparison between hybrid dataflow implementations and traditional shared memory implementations. We use DaSH not only to evaluate the ADF model, but to also compare it with other two hybrid dataflow models in order to identify the advantages and shortcomings of such models, and motivate further research on their characteristics.\r\nFinally, we study applicability of hybrid dataflow models for parallelization of the game engine. We show that hybrid dataflow models decrease the complexity of the parallel game engine implementation by eliminating or restructuring the explicit synchronization that is necessary in shared memory implementations. The corresponding implementations also exhibit good scalability and better speedup than the shared memory parallel implementations, especially in the case of a highly congested game world that contains a large number of game objects. Ultimately, on an eight core machine we were able to obtain 4.72x speedup compared to the sequential baseline, and to improve 49% over the lock-based parallel implementation based on work-sharing.<\/jats:p>\n                <jats:p>Con el reciente cambio en el dise\u00f1o de los procesadores de prop\u00f3sito general pasando del aumento de frecuencia al incremento del n\u00famero de n\u00facleos, la programaci\u00f3n paralela se ha convertido en importante no solo para la comunidad cient\u00edfica sino tambi\u00e9n para la programaci\u00f3n en general. Este hecho ha enfatizado la importancia de la programabilidad de los modelos actuales de programaci\u00f3n paralela, cuyo objetivo era el rendimiento. Pronto se observ\u00f3 la necesidad de nuevos modelos de programaci\u00f3n, para hacer factible la programaci\u00f3n paralela a toda la comunidad. Transactional Memory (TM) es un ejemplo de dicho objetivo. Supone una gran mejora sobre cualquier m\u00e9todo anterior de sincronizaci\u00f3n en t\u00e9rminos de programabilidad, con una posible reducci\u00f3n del rendimiento como coste. La raz\u00f3n principal de dicha degradaci\u00f3n es el sobrecoste de la ejecuci\u00f3n transaccional. Nuestro trabajo en la paralelizaci\u00f3n del motor del juego Quake es un claro ejemplo de este problema. Demostramos que Software Transactional Memory es superior en t\u00e9rminos de programabilidad a los modelos de programaci\u00f3n basados en locks, pero que el rendimiento es entorpecido por el sobrecoste introducido por TM. Mientras tanto, se ha invertido un importante esfuerzo de investigaci\u00f3n para superar dicho problema. Nuestra soluci\u00f3n se dirige hacia la mejora del rendimiento del c\u00f3digo transaccional reduciendo los conflictos con la informaci\u00f3n contenida en las transacciones. La idea se basa en la organizaci\u00f3n del c\u00f3digo en el cual la informaci\u00f3n conflictiva es promocionada a se\u00f1ales del flujo de datos que coordinan la ejecuci\u00f3n de las transacciones. La contribuci\u00f3n principal de esta tesis es Atomic Dataflow Model (ADF), un nuevo modelo de programaci\u00f3n para C\/C++ basado en tareas que integra abstracciones de flujo de datos en el modelo de programaci\u00f3n de la memoria compartida. El modelo ADF provee construcciones del lenguaje que permiten al programador la definici\u00f3n del programa como un conjunto de tareas, adem\u00e1s de la definici\u00f3n expl\u00edcita de las dependencias de datos para cada tarea. La informaci\u00f3n de dependencia de la tarea se transmite al runtime de ADF, que construye un grafo de tareas que es el que controla la ejecuci\u00f3n de un programa. Adicionalmente, el modelo ADF permite que las tareas compartan informaci\u00f3n. La idea principal es que la computaci\u00f3n es activada por el flujo de datos entre tareas, pero que dentro de una tarea la ejecuci\u00f3n ocurre haciendo actualizaciones at\u00f3micas a un estado com\u00fan mutable. Para conseguir este fin, el modelo ADF utiliza TM, que garantiza la atomicidad en las modificaciones de la memoria compartida. La segunda contribuci\u00f3n es DaSH, el primer conjunto de benchmarks para los modelos de programaci\u00f3n de flujo de datos h\u00edbridos y los de memoria compartida. DaSH contiene 11 benchmarks, cada uno representativo de uno de los Berkeley dwarfs que captura patrones de comunicaciones y procesamiento comunes en un amplio rango de aplicaciones emergentes. DaSH incluye implementaciones secuenciales y de memoria compartida basadas en OpenMP y TBB que facilitan la comparaci\u00f3n entre los modelos h\u00edbridos de flujo de datos e implementaciones de memoria compartida. Nosotros usamos DaSH no solo para evaluar ADF, sino tambi\u00e9n para compararlo con otros dos modelos h\u00edbridos para identificar sus ventajas. Finalmente, estudiamos la aplicabilidad de dichos modelos h\u00edbridos para la paralelizaci\u00f3n del motor del juego. Mostramos que disminuyen la complejidad de la implementaci\u00f3n paralela, eliminando o reestructurando la sincronizaci\u00f3n expl\u00edcita que es necesaria en las implementaciones de memoria compartida. Tambi\u00e9n se observa una buena escalabilidad y una aceleraci\u00f3n mejor, especialmente en el caso de un ambiente de juego muy cargado. En \u00faltima instancia, sobre una m\u00e1quina con ocho n\u00facleos se ha obtenido una aceleraci\u00f3n del 4.72x comparado con el c\u00f3digo secuencial, y una mejora del 49% sobre la implementaci\u00f3n paralela basada en locks.<\/jats:p>","DOI":"10.5821\/dissertation-2117-95538","type":"dissertation","created":{"date-parts":[[2023,7,19]],"date-time":"2023-07-19T01:34:36Z","timestamp":1689730476000},"approved":{"date-parts":[[2014,11,20]]},"source":"Crossref","is-referenced-by-count":0,"title":["Atomic dataflow model"],"prefix":"10.5821","author":[{"given":"Vladimir","family":"Gajinov","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"3865","container-title":[],"original-title":[],"contributor":[{"sequence":"additional","affiliation":[],"role":[null]}],"deposited":{"date-parts":[[2026,1,26]],"date-time":"2026-01-26T06:27:34Z","timestamp":1769408854000},"score":1,"resource":{"primary":{"URL":"https:\/\/hdl.handle.net\/2117\/95538"}},"subtitle":[],"editor":[{"given":"Eduard","family":"Ayguad\u00e9 Parra","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"editor"}]},{"given":"Osman Sabri","family":"Unsal","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"editor"}]},{"given":"Adri\u00e1n","family":"Cristal Kestelman","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"editor"}]}],"short-title":[],"issued":{"date-parts":[[null]]},"references-count":0,"URL":"https:\/\/doi.org\/10.5821\/dissertation-2117-95538","relation":{},"subject":[]}}