Combinational Equivalence Checking (CEC) is a crucial technique in electronic design automation for verifying the functional equivalence of combinational circuits. Recently, combinational circuit design increasingly incorporates more complex arithmetic structures, commonly known as datapath circuits. However, existing state-of-the-art tools often exhibit subpar performance in solving datapath CEC problems. To further advance the exploration on datapath CEC process, this study introduces PDP-CEC (Parallel Dynamic Partitioning Combinational Equivalence Checking), a novel parallel CEC approach integrating circuit partitioning and dynamic task scheduling into the CEC process, enhancing the efficiency of CEC for datapath circuits. PDP-CEC introduces an innovative method for selecting critical nodes to split the search space of the CEC problem, facilitating the efficient generation of numerous independent subproblems. Meanwhile, a dynamic task scheduling strategy is implemented in PDP-CEC to ensure load balancing and prevent hard-to-solve subproblems from stalling the entire process. Compared to the most advanced tools such as ABC and HybridCEC, PDP-CEC significantly accelerates CEC process, achieving speedups ranging from $5.11 x$ to $125.27 x$, while effectively solving approximately three times more datapath CEC problems. With excellent scalability, PDP-CEC shows substantial improvements in combinational equivalence checking for datapath circuits, offering an efficient parallel approach to meet the demands of large-scale datapath CEC tasks.

The performance of the enumeration-based sub-graph matching, which searches all isomorphic subgraphs in the data graph, is crucial to various applications. The upper bound of the complexity for the enumeration-based method is exponential to the number of query graph vertices, denoted as$n$. We propose a novel subgraph matching algorithm called the Isolated Vertices Exploration (IVE). The IVE leverages isolated vertices during the reordering and enumeration phases, thereby significantly accelerating the subgraph matching process. During the enumeration, the isolated vertices can be matched by using a quick bipartite graph matching algorithm. Consequently, the complexity of matching the remaining non-isolated vertices is exponential to the number of non-isolated vertices, denoted as$n^{\prime}$. For the reordering, we designed the Maximum Deleted Edges (MDE) to minimize$n^{\prime}$. MDE iteratively selects the query vertex with the maximum edges. According to the experimental results,$n^{\prime}$is less than$0.8n$for 99.8% of arbitrary graphs. Moreover, IVE outperforms the state-of-the-art algorithms in various scenarios with different sizes, sparsities and fields, achieving a performance speedup of up to 80.3x.

Subgraph matching is a challenging NP-complete problem that involves finding identical subgraphs of a query graph$q$in a larger data graph$G$. It has numerous applications in diverse fields, including social and biological networks. However, existing subgraph matching algorithms assume that the graph structure is fixed, which limits their performance in solving more difficult matching cases. To address this issue, we propose a novel approach called Dynamic Graph Editing (DGE), which dynamically edits the query graph to optimize the subgraph matching algorithm. Based on this approach, we introduce an efficient enumeration method called Dynamic Graph Editing Enumeration, which significantly improves the performance of the algorithm. Our experimental results show that DGE outperforms current state-of-the-art algorithms in terms of computational efficiency and ability to solve more complex subgraph matching cases.

Nowadays, the ever-increasing volume of graph-structured data such as social networks, graph databases and knowledge graphs requires to be processed efficiently and scalably. These natural graphs commonly found in the real world have highly skewed power-law degree distribution and are called power-law graphs. The subgraph-centric programming model is a promising approach applied in many state-of-the-art distributed graph computing frameworks. However, the performance of subgraph-centric frameworks is limited when processing large-scale power-law graphs. When deployed to the subgraph-centric framework, existing graph partitioning algorithms are not suitable for power-law graphs. In this paper, we present a novel distributed graph computing framework, DRONE (Distributed gRaph cOmputiNg Engine), which leverages the subgraph-centric model and the vertex-cut graph partitioning strategy. DRONE also supports the fault tolerance mechanism to accommodate the increasing scale of machines with negligible overhead (6.48% on average). We further study the execution workflow of DRONE and propose an efficient and balanced graph partition algorithm (EBV) for DRONE. Experiments show that DRONE reduces the running time on real-world graphs by 25.6%, on average, compared to the state-of-the-art distributed graph computing frameworks. In addition, the EBV graph partition algorithm reduces the replication factor by at least 21.8% than other self-based partition algorithms. Our results indicate that DRONE has excellent potential in processing large-scale power-law graphs.

Few-shot image generative adaptation, which finetunes well-trained generative models on limited examples, is of practical importance. The main challenge is that the few-shot model easily becomes overfitting. It can be attributed to two aspects: the lack of sample diversity for the generator and the failure of fidelity discrimination for the discriminator. In this paper, we introduce two novel methods to solve the diversity and fidelity respectively. Concretely, we propose dynamic weighted semantic correspondence to keep the diversity for the generator, which benefits from the richness of samples generated by source models. To prevent discriminator overfitting, we propose coupled training paradigm across the source and target domains to keep the feature extraction capability of the discriminator backbone. Extensive experiments show that our method outperforms previous methods both on image quality and diversity significantly.

Nowadays, the parallel processing of power-law graphs is one of the biggest challenges in the field of graph computation. The subgraph-centric programming model is a promising approach and has been applied in many state-of-the-art distributed graph computing frameworks. The graph partition algorithm plays an important role in the overall performance of subgraph-centric frameworks. However, traditional graph partition algorithms have significant difficulties in processing large-scale power-law graphs. The major problem is the communication bottleneck found in many subgraph-centric frameworks. Detailed analysis indicates that the communication bottleneck is caused by the huge communication volume or the extreme message imbalance among partitioned subgraphs. The traditional partition algorithms do not consider both factors at the same time, especially on power-law graphs. In this paper, we propose a novel efficient and balanced vertex-cut graph partition algorithm (EBV) which grants appropriate weights to the overall communication cost and communication balance. We observe that the number of replicated vertices and the balance of edge and vertex assignment have a great influence on communication patterns of distributed subgraph-centric frameworks, which further affect the overall performance. Based on this insight, We design an evaluation function that quantifies the proportion of replicated vertices and the balance of edges and vertices assignments as important parameters. Besides, we sort the order of edge processing by the sum of end-vertices' degrees from small to large. Experiments show that EBV reduces replication factor and communication by at least 21.8% and 23.7% respectively than other self-based partition algorithms. When deployed in the subgraph-centric framework, it reduces the running time on power-law graphs by an average of 16.8% compared with the state-of-the-art partition algorithm. Our results indicate that EBV has a great potential in improving the performance of subgraph-centric frameworks for the parallel large-scale power-law graph processing.