Efficient processing of streaming graphs is crucial to improve system performance. Due to the highly irregular and frequent access to data in streaming graph processing, existing cache management methods are difficult to accurately predict cache behavior, resulting in serious cache misses. To address the issues, we propose CEGraph, an efficient cache management approach for streaming graph processing. Specifically, for graph data, we propose a cache replacement policy based on vertex importance. This policy accurately evaluates the importance of vertices in the incremental processing of streaming graphs from our proposed three factors: the association degree of affected state of a vertex, the path distance of a vertex, and whether a vertex will be updated. Vertices with high importance are identified and kept in the cache to reduce cache thrashing. Experimental results reveal that compared with LRU, DRRIP and Grasp, CEGraph reduces the LLC misses by an average of 22.93% (maximum 34.27%), 20.87% and 11.91%, respectively. Compared with the state-of-the-art cache management method P-OPT, CEGraph reduces the LLC misses by 6.46% on average, therefore demonstrating the effectiveness of CEGraph.

There are usually a large number of concurrent graph queries (CGQs) requirements in streaming graphs. However, existing graph processing systems mainly optimize a single graph query in streaming graphs or CGQs in static graphs. They have a large number of redundant computations and expensive memory access overhead, and cannot process CGQs in streaming graphs efficiently. To address these issues, we propose PMGraph , a software-hardware collaborative accelerator for efficient processing of CGQs in streaming graphs. First, PMGraph centers on fine-grained data, selects graph queries that meet the requirements through vertex data, and utilizes the similarity between different graph queries to merge the same vertices they need to process to address the problem of a large amount of repeated access to the same data by different graph queries in CGQs, thereby reducing memory access overhead. Furthermore, it adopts the update strategy that regularizes the processing order of vertices in each graph query according to the order of the vertex dependence chain, consequently effectively reducing redundant computations. Second, we propose a CGQs-oriented scheduling strategy to increase the data overlap when different graph queries are processed, thereby further improving the performance. Finally, PMGraph prefetches the vertex information according to the global active vertex set Frontier of all graph queries, hiding the memory access latency. It also provides prefetching for the same vertices that need to be processed by different graph queries, reducing the memory access overhead. Compared with the state-of-the-art concurrent graph query software systems Kickstarter-C and Tripoline, PMGraph achieves average speedups of 5.57× and 4.58×, respectively. Compared with the state-of-the-art hardware accelerators Minnow, HATS, LCCG, and JetStream, PMGraph achieves the speedup of 3.65×, 3.41×, 1.73×, and 1.38× on average, respectively. Experimental results show that our proposed PMGraph outperforms the state-of-the-art concurrent graph processing systems and hardware accelerators.

Streaming graph processing needs to timely evaluate continuous queries. Prior systems suffer from massive redundant computations due to the irregular order of processing vertices influenced by updates. To address this issue, we propose ACGraph, a novel streaming graph processing approach for monotonic graph algorithms. It maintains dependence trees during runtime, and makes affected vertices processed in a top-to-bottom order in the hierarchy of the dependence trees, thus normalizing the state propagation order and coalescing of multiple propagation to the same vertices. Experimental results show that ACGraph reduces the number of updates by 50% on average, and achieves the speedup of 1.75~7.43× over state-of-the-art systems.

The hardware description of circuits usually contains many loops. Register transfer level (RTL) simulation is a critical step to verify the correctness of circuits and is time consuming. Thus, it is necessary to speed up its process. However, the speedup of existing RTL simulation acceleration techniques is usually small. Although the speedup of hardware acceleration is large, the hardware cost is high. Some methods utilize performance models without performing RTL simulation to obtain rough simulation performance and have a large speedup. However, they do not support functional verification. In order to address the problems, we propose a loop-oriented RTL simulation acceleration approach based on code instrumentation for designs synthesized by high-level synthesis. Our approach reduces the RTL simulation time by skipping a large number of repeated loop iterations, and maintains high accuracy for the prediction of the number of cycles by reserving some loop iterations. We establish a performance prediction model and an interval value formula for skipping loop iterations. We conduct experiments on the MachSuite benchmark. The results show that for the RTL simulation of single data processing and batch data processing, the average speedup of our approach can reach$7.49\times $and$43.3\times $, respectively, and the average prediction errors of the number of cycles are 1.71% and 1.06%, respectively. It also reveals that the interval value obtained by our approach for skipping loop iterations can quickly and effectively balance between the accuracy of prediction of the number of cycles and speedup. Compared to the state-of-the-art approach ESSENT, the speedup of our approach is better and the accuracy of prediction of the number of cycles remains at the same level as that of performance models.