In recent years, extensive research has been carried out on real-time typed scheduling and analysis of parallel tasks represented as directed acyclic graphs (DAGs) executed on heterogeneous multicores. Although previous studies have examined the schedulability of typed DAG tasks, they still encounter pessimism caused by interference from other tasks. In this article, we explore the worst case response time (WCRT) analysis of typed scheduling for DAG tasks under global scheduling. Here, each vertex in a typed DAG task experiences interference from within itself as well as from higher priority tasks. First, we propose an efficient method to bound the WCRT of typed DAG tasks based on the state-of-the-art parallel task analysis approach. Then, we discover a technique to mitigate the pessimism caused by other tasks, albeit in a nonoptimal manner. Finally, we conduct experiments using randomly generated typed DAG tasks to evaluate the performance of our proposed methods. The results indicate that our proposed approach can yield less pessimistic WCRT under global scheduling.

Dynamic graph management (DGM) systems are designed to effectively handle changing graph data, which is a fundamental problem for many graph-based applications. Recently, researchers have designed GPU-based solutions for DGM and its downstream applications, thanks to GPUs' massive parallelism power. However, there is a lack of universal models that summarize the features and design principles of GPU-accelerated DGM systems. Additionally, existing studies test GPU-based DGM systems without unified metrics and workloads. Under this circumstance, we propose a conceptual model for GPU-accelerated DGM to demonstrate a DGM system's components, key primitives, and optimization choices. Next, we evaluate six representative systems, testing their update and query performance with unified metrics and workloads of different algorithmic behaviors. We also extend existing systems to seek insight to fill the current research gap in multi-GPU support, concurrency control, resource utilization, and so on. Our evaluation yielded new insights on the pros and cons of different systems: (1) Hashing-based systems perform best for graph updates but may not be suitable for all applications. (2) Finding a system that fits all workloads is challenging, and hybrid data storage may be a solution. (3) To select the most suitable DGM system for a specific workload, it is essential to consider hardware-related metrics. Finally, we provide recommendations and suggestions for future studies based on our experimental results and observations.

Subgraph isomorphism plays a significant role in many applications, such as social networks and bioinformatics. However, due to the inherent NP-hardness, it becomes challenging to compute matches efficiently in large real-world graphs. Many researchers have attempted to solve this problem with the help of new hardware. Nevertheless, most of them focus on GPU. Due to the dataflow feature and burst I/O optimization, FPGA is a potential competitor to speed up subgraph isomorphism. However, there are very few subgraph matching algorithms on FPGA. In this paper, we present an efficient FPGA-friendly Subgraph Isomorphism algorithm FASI, designed on CPU- FPGA heterogeneous platform which leverages FPGA's features. Unlike the existing FPGA-based method FAST, we adopt the worst-case-optimal-join-based pipeline design. First, we propose an FPGA-friendly data structure LPCSR for efficient access to neighbor lists. Second, we offer a joint parallelized pipeline strategy to accelerate matching process. Third, we propose a memory coalescing mechanism and a space-saving pre-allocated write back strategy. Our experiments on both synthetic and real graphs show that FASI outperforms other state-of-the-art subgraph matching algorithms on CPU, GPU and FPGA.