Hazem had a paper entitled “Combining Dataflow Applications and Real-time Task Sets on Multi-core Platforms” accepted at the 2017 Workshop on Software and Compilers for Embedded Systems (SCOPES). This paper is a short overview of his PhD dissertation, which will be defended in Porto on May 23, and explains an approach to map and schedule a multi-/many-core system containing both applications described as traditional real-time task sets and synchronous data-flow graphs. Hazem’s approach is to convert the data-flow graph into a periodic real-time task set to unify the models before mapping, which enables him to leverage existing real-time analysis techniques and schedulers. However, converting a complex data-flow graph into a periodic task set may result in a large number of tasks, resulting in long analysis times. To mitigate this problem, he proposes a slack-based merging algorithm that allows the number of tasks to be reduced by carefully sacrificing parallelism in the data-flow graph, subject to its latency and throughput constraints. Lastly, the resulting unified real-time task set is mapped to a multi-/many-core platform interconnected by a TDM NoC using a sensitive-path-first algorithm, which first allocates tasks derived from the original data-flow graph that have the highest impact on its execution and schedulability. It is also able to exploit parallelism in graph during mapping.
We hope you enjoy the paper and wish Hazem all the best for his upcoming defense.
We just received the good news that Hazem’s article “ Reducing the Complexity of Dataflow Graphs using Slack-based Merging” has been accepted for publication in ACM Transactions on Design Automation of Electronic Systems (TODAES). The article addresses an important problem when working with synchronous data-flow (SDF) graphs, namely that the size of the graph explodes when transforming it to its equivalent homogeneous (HSDF) representation, which prevents any design or analysis algorithms requiring this transformation as a first step from scaling to larger graphs. In the scope of Hazem’s work, this has caused problems when converting an SDF graph into a set of independent periodic real-time tasks.
This article proposes a heuristic algorithm to reduce the size of the resulting HSDF graph prior to analysis by merging actors in the graph, thereby speeding up analysis algorithms using the resulting graph. Three key properties of the algorithm are: 1) it cannot violate the latency or throughput requirements of the original graph, 2) it cannot cause deadlock in the resulting merged graph, and 3) only HSDF actors corresponding to firings of the same SDF actor can be merged to enable the resulting merged graph to be efficiently used by mapping algorithms. The behavior of the algorithm is evaluated with applications from the SDF3 benchmark suite and it is compared to results of an optimal exhaustive merging algorithm for smaller graphs.
Last year, my PhD student Hazem Ali got a HiPEAC collaboration grant sponsoring a three month visit in the Electronic Systems group at Eindhoven University of Technology, hosted by Dr. Sander Stuijk. The topic of the joint research is related to the borderland between data-flow and traditional real-time analysis. On page 15 in the latest issue of the HiPEAC Newsletter, you can read more about his stay.
Today, we congratulate Hazem Ali for having a paper accepted at PDP 2015. The paper is entitled “Generalized Extraction of Real-Time Parameters for Homogeneous Synchronous Dataflow Graphs” and proposes a heuristic methodology for extracting real-time parameters, such as periods, deadlines and offsets, for applications specified as homogeneous synchronous data-flow (HSDF) graphs. The benefit of the approach is that it enables HSDF applications to be analyzed using traditional real-time techniques and scheduled with common real-time schedulers, such as earliest-deadline first.
Today, we congratulate Hazem Ali for having his first paper accepted at RTCSA. The paper is entitled “Critical-Path-First Based Allocation of Real-Time Streaming Applications on 2D Mesh-Type Multi-Cores” and proposes a mapping strategy for streaming applications, represented as acyclic data-flow graphs with throughput requirements, to multi-core architectures under partitioned EDF scheduling. The key idea is to first map tasks on the critical-paths of the application to minimize their execution time and thereby increasing the chance to satisfy the throughput constraint. The camera-ready version is available here.
Hazem Ali is a PhD student at the CISTER-ISEP Research Unit in Porto, supervised by Luis Miguel Pinho and myself, and this paper is a result of my six month visit there last year and the fruitful collaboration it has resulted in afterwards.