A Mapping-Scheduling Algorithm for Hardware Acceleration on Reconfigurable Platforms

Reconfigurable platforms are a promising technology that offers an interesting trade-off between flexibility and performance, which many recent embedded system applications demand, especially in fields such as multimedia processing. These applications typically involve multiple ad-hoc tasks for hardware acceleration, which are usually represented using formalisms such as Data Flow Diagrams (DFDs), Data Flow Graphs (DFGs), Control and Data Flow Graphs (CDFGs) or Petri Nets. However, none of these models is able to capture at the same time the pipeline behavior between tasks (that therefore can coexist in order to minimize the application execution time), their communication patterns, and their data dependencies. This paper proves that the knowledge of all this information can be effectively exploited to reduce the resource requirements and the timing performance of modern reconfigurable systems, where a set of hardware accelerators is used to support the computation. For this purpose, this paper proposes a novel task representation model, named Temporal Constrained Data Flow Diagram (TCDFD), which includes all this information. This paper also presents a mapping-scheduling algorithm that is able to take advantage of the new TCDFD model. It aims at minimizing the dynamic reconfiguration overhead while meeting the communication requirements among the tasks. Experimental results show that the presented approach achieves up to 75% of resources saving and up to 89% of reconfiguration overhead reduction with respect to other state-of-the-art techniques for reconfigurable platforms.

Verificación de extensiones de Redes de Petri con precios, tiempo y múltiples instancias

Las redes de Petri son un lenguaje formal muy adecuado para la modelizacíon, ańalisis y verificacíon de sistemas concurrentes con infinitos estados. En particular, son muy apropiadas para estudiar las propiedades de seguridad de dichos sistemas, dadas sus buenas propiedades de decidibilidad. Sin embargo, en muchas ocasiones las redes de Petri carecen de la expresividad necesaria para representar algunas caracteŕısticas fundamentales de los sistemas que se manejan hoy en d́ıa, como el manejo de tiempo real, costes reales, o la presencia de varios procesos con un ńumero no acotado de estados ejecut́andose en paralelo. En la literatura se han definido y estudiado algunas extensiones de las redes de Petri para la representaci ́on de las caracteŕısticas anteriores. Por ejemplo, las “Redes de Petri Temporizadas” [83, 10](TPN) incluyen el manejo de tiempo real y las ν-redes de Petri [78](ν-PN) son capaces de representar un ńumero no acotado de procesos con infinitos estados ejecut́andose concurrentemente. En esta tesis definimos varias extensiones que réunen estas dos caracteŕısticas y estudiamos sus propiedades de decidibilidad. En primer lugar definimos las “ν-Redes de Petri Temporizadas”, que réunen las caracteŕısticas expresivas de las TPN y las ν-PN. Este nuevo modelo es capaz de representar sistemas con un ńumero no acotado de procesos o instancias, donde cada proceso es representado por un nombre diferente, y tiene un ńumero no acotado de relojes reales. En este modelo un reloj de una instancia debe satisfacer ciertas condiciones (pertenecer a un intervalo dado) para formar parte en el disparo de una transicíon. Desafortunadamente, demostramos que la verificacíon de propiedades de seguridad es indecidible para este modelo...