Automated Heuristic Design (AHD) using Large Language Models (LLMs) has achieved notable success in the past two years. Despite the effectiveness of existing approaches, they only design a single heuristic to serve all problem instances, often inducing poor generalization across different distributions or sizes. To address this issue, we propose Automated Heuristic Set Design (AHSD), a new methodology for LLM-driven AHD. The aim of AHSD is to automatically design a small-sized complementary heuristic set to serve diverse problem instances, such that each problem instance could be optimized by at least one heuristic in this set. We propose Evolution of Heuristic Set (EoH-S), which realizes AHSD using an evolutionary search framework. It incorporates a complementary population management and a memetic search to design a set of heuristics. Extensive experiments on online bin packing, traveling salesman problem, and capacitated vehicle routing problem show that EoH-S consistently outperforms existing AHD methods. The resulting heuristics exhibit complementary performance across instances of varying sizes and distributions.

Zehua Pei, Hui-Ling Zhen, Lancheng Zou, Xianzhi Yu, Wulong Liu, Sinno Jialin Pan, Mingxuan Yuan, Bei Yu. Proceedings of the 64th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers). 2026.

Timing-driven detailed placement is a critical stage in very large scale integrated (VLSI) design, aiming to locally adjust cell positions to further improve circuit timing performance. Existing methods commonly adopt proxy metrics as optimization objectives, such as weighted wirelength and approximate delay. However, these surrogate metrics are not fully aligned with the final timing metrics obtained through static timing analysis (STA), often leading to suboptimal timing results. Besides, methods based directly on STA tools suffer from very low search efficiency, making the cost of timing optimization prohibitive. To address these issues, we propose an effective timing-driven detailed placement method via TimingMask-guided path-level optimization. One core of our method is the TimingMask guidance mechanism, which integrates both arc delay and path slack information based on the RC timing model, thereby providing more targeted and effective guidance for refinement of critical cells. Meanwhile, our method adopts a path-level timing evaluation strategy with incremental updates, accelerating the optimization process while preserving timing accuracy. Experimental results on the ICCAD 2015 contest benchmarks demonstrate that our method significantly outperforms state-of-the-art detailed placement methods such as DREAMPlace4.0 DP, achieving an average improvement of 25.3% in total negative slack (TNS) and 21.7% in worst negative slack (WNS).

The clustering-based placement framework has demonstrated promising potential in improving the efficiency and quality of very-large-scale integration (VLSI) placement. However, existing methods typically impose unified and rule-based constraints on different clusters, overlooking the unique intra-and inter-cluster connection properties that vary across clusters, which leads to suboptimal results. To address this challenge and promote effective PPA optimization, we introduce an innovative PPA-driven placement paradigm with mixed-grained Adaptive Cluster Constraints Optimization (ACCO), which applies constraints with customized constraint tightness to different clusters, balancing local and global interactions for improved placement performance. Specifically, we propose a novel eBound model with quantified constraint tightness, combined with a Bayesian optimizer to dynamically adjust the constraints for each cluster based on PPA outcomes, which are ultimately passed on to the final flat placement. Experimental results on benchmarks across various domains show that our methods can achieve up to 62%, 97% and 25% improvements in post-route WNS, TNS and power compared to existing methods.

Placement is a vital step in the physical design flow of very large-scale integration (VLSI) circuits. GPU-accelerated analytical placement algorithms, such as DREAMPlace, have achieved high-quality performance with dramatic speedup. The algorithm configurations of the analytical placer have a significant impact on its convergence and final performance. However, its tuning process is difficult and time-consuming. Recently, AutoDMP tries to search for optimal static algorithm configurations using Bayesian optimization, but the performance is still limited due to its static strategy, which cannot leverage information during algorithm execution. In this paper, we propose the dynamic algorithm configuration framework for DREAMPlace (DACDMP), using reinforcement learning (RL) to learn the dynamic control policy of the most critical hyperparameter, i.e., the learning rate. Moreover, to address the insufficiency of optimization, we increase the number of optimization steps in each Lagrangian relaxation problem, thereby improving the solution’s optimality. DACDMP outperforms the current leading methods, i.e., DREAMPlace 4.0, AutoDMP, and Xplace. For example, compared to DREAMPlace 4.0, it achieves an average improvement of 2.75% in wirelength, 18.74% in worst negative slack (WNS), 44.60% in total negative slack (TNS), and 29.39% in the number of violation points on the ICCAD 2015 benchmark.

Hybrid bonding (HB) in 3D ICs enables scaling but introduces overlap challenges from large pitch requirements. Existing legalization methods use exhaustive sliding-window scanning, resulting in significant computational inefficiency. To address this, we propose a reinforcement learning (RL) approach that adaptively selects subregions for targeted displacement optimization. The learned policy generalizes to unseen designs without fine-tuning. Experimental results on open-source and industrial benchmarks show our method fully eliminates overlaps with minimal displacement and reduced runtime compared with baselines.

Considering the challenges faced by large language models (LLMs) in logical reasoning and planning, prior efforts have sought to augment LLMs with access to external solvers. While progress has been made on simple reasoning problems, solving classical constraint satisfaction problems, such as the Boolean satisfiability problem (SAT) and graph coloring problem (GCP), remains difficult for off-the-shelf solvers due to their intricate expressions and exponential search spaces. In this paper, we propose a novel differential logic layer-aided language modeling (DiLA) approach, where logical constraints are integrated into the forward and backward passes of a network layer, providing another option for LLM tool learning. In DiLA, LLM aims to transform the language description to logic constraints and identify initial solutions of the highest quality, while the differential logic layer focuses on iteratively refining the LLM-prompted solution. Leveraging the logic layer as a bridge, DiLA enhances the logical reasoning ability of LLMs on a range of reasoning problems encoded by Boolean variables, guaranteeing the efficiency and correctness of the solution process. We evaluate the performance of DiLA on three classic constraint satisfaction problems and empirically demonstrate its consistent outperformance against existing prompt-based and solver-aided approaches.

In modern intelligent transportation systems (ITS), particularly in freight transportation and logistics, real-time route planning is crucial. It presents unique challenges driven by high uncertainty in service requests, where the number of service customers can vary drastically, ranging from hundreds to thousands. Existing neural methods struggle to maintain performance under such significant variations, which severely limits their practical applicability. To address this crucial shortcoming, this work proposes a novel Instance-Conditioned Adaptation Model (ICAM) designed for better large-scale generalization. In particular, we design a simple yet efficient instance-conditioned adaptation function that adjusts the policy based on the specific geometry and density of the current traffic scenario to improve model adaptability with minimal computational overhead. Furthermore, we propose a powerful yet low-complexity instance-conditioned adaptation module to generate better solutions for instances across various scales. Extensive experiments on synthetic, benchmark, and real-world instances demonstrate that ICAM can consistently achieve promising generalization performance across four widely studied large-scale route planning scenarios. Notably, our proposed method delivers high-quality solutions with remarkably fast inference speed, providing a scalable and efficient solution for real-time intelligent transportation operations. Our code is available at <uri xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">https://github.com/CIAM-Group/ICAM</uri>

Recently, printed circuit board (PCB) placement has emerged as a significant challenge since the scale of PCB designs has rapidly enlarged. Furthermore, the presence of various types of constraints with differing tolerance priorities hampers the automation of PCB layout design, necessitating substantial manual effort. To address this problem, we introduce a novel agent-based framework that automatically generates PCB layouts meeting industrial constraints through user interactions. This framework includes two main agents: a reinforcement learning (RL)-based agent for layout inference and fine-tuning, and a large language model (LLM)-based agent for interactive optimization. Experimental results on 17 industrial tasks show that our framework outperforms other state-of-the-art methods.

Electronic Design Automation (EDA) is essential for IC design and has recently benefited from AI-based techniques to improve efficiency. Logic synthesis, a key EDA stage, transforms high-level hardware descriptions into optimized netlists. Recent research has employed machine learning to predict Quality of Results (QoR) for pairs of And-Inverter Graphs (AIGs) and synthesis recipes. However, the severe scarcity of data due to a very limited number of available AIGs results in overfitting, significantly hindering performance. Additionally, the complexity and large number of nodes in AIGs make plain GNNs less effective for learning expressive graph-level representations. To tackle these challenges, we propose MTLSO - a Multi-Task Learning approach for Logic Synthesis Optimization. On one hand, it maximizes the use of limited data by training the model across different tasks. This includes introducing an auxiliary task of binary multi-label graph classification alongside the primary regression task, allowing the model to benefit from diverse supervision sources. On the other hand, we employ a hierarchical graph representation learning strategy to improve the model's capacity for learning expressive graph-level representations of large AIGs, surpassing traditional plain GNNs. Extensive experiments across multiple datasets and against state-of-the-art baselines demonstrate the superiority of our method, achieving an average performance gain of 8.22% for delay and 5.95% for area.

This paper proposes smaRTLy: a new optimization technique for multiplexers in Register-Transfer Level (RTL) logic synthesis. Multiplexer trees are very common in RTL designs, and traditional tools like Yosys optimize them by traversing the tree and monitoring control port values. However, this method does not fully exploit the intrinsic logical relationships among signals or the potential for structural optimization. To address these limitations, we develop innovative strategies to remove redundant multiplexer trees and restructure the remaining ones, significantly reducing the overall gate count. We evaluate smaRTLy on the IWLS-2005 and RISC-V benchmarks, achieving an additional 8.95% reduction in AIG area compared to Yosys. We also evaluate smaRTLy on an industrial benchmark in the scale of millions of gates, results show that smaRTLy can remove 47.2% more AIG area than Yosys. These results demonstrate the effectiveness of our logic inferencing and structural rebuilding techniques in enhancing the RTL optimization process, leading to more efficient hardware designs.

Large Language Models (LLMs) have revolutionized language tasks but pose significant deployment challenges due to their substantial computational demands during inference. The hardware configurations of existing LLM serving systems do not optimize for the different computational and bandwidth needs of the prefill and decoding phases in LLM inference, leading to inefficient resource use and increased costs. In this paper, we systematically investigate promising hardware configurations for LLM inference serving. We develop a simulator that models the performance and cost across different hardware solutions and introduce a customized design space exploration framework to identify optimal setups efficiently. By aligning hardware capabilities with the specific demands of the prefill and decoding phases, we achieve $13 \%$ cost savings and over $4 \times$ throughput improvements compared to conventional serving system setups.

We introduce the ReMaP framework, which generates expert-quality macro placements through recursively prototyping and periphery-guided relocating. A key innovation is ABPlace, an angle-based analytical method that arranges macros along an ellipse to facilitate a rough distribution near the periphery, while optimizing dataflow, minimizing overlap, and ensuring convergence. Based on the results of ABPlace, an efficient heuristic is proposed to position macros along the chip’s periphery, mirroring practices often employed by experts. Our framework outperforms three leading macro placers in both WNS and TNS across eight test cases, achieving improvements up to 34.15% in WNS and 65.39% in TNS, as tested on the popular OpenROAD-flow-scripts infrastructure. Additionally, our parameter autotuning method further improves timing by 8.75%.

The Circuit Satisfiability (CSAT) problem, a variant of the Boolean Satisfiability (SAT) problem, plays a critical role in integrated circuit design and verification. However, existing SAT solvers, optimized for Conjunctive Normal Form (CNF), often struggle with the intrinsic complexity of circuit structures when directly applied to CSAT instances. To address this challenge, we propose a novel preprocessing framework that leverages advanced logic synthesis techniques and a reinforcement learning (RL) agent to optimize CSAT problem instances. The framework introduces a cost-customized Look-Up Table (LUT) mapping strategy that prioritizes solving efficiency, effectively transforming circuits into simplified forms tailored for SAT solvers. Our method achieves significant runtime reductions across diverse industrial-scale CSAT benchmarks, seamlessly integrating with state-of-the-art SAT solvers. Extensive experimental evaluations demonstrate up to $63 \%$ reduction in solving time compared to conventional approaches, highlighting the potential of EDAdriven innovations to advance SAT-solving capabilities.

Boolean decomposition is a powerful technique in logic synthesis that breaks down Boolean functions into simpler components. Decomposition-based logic synthesis yields high-quality results and is particularly effective when combined with small-window optimization methods in Gate-Inverter Graphs (GIG). However, the efficiency limitations of current methods have constrained their applicability in handling large and complex logic. To address this challenge, we propose a novel framework, called EDGE, which leverages modern database techniques to accelerate Boolean decomposition, thereby achieving improved synthesis results while maintaining high efficiency. Experimental results demonstrate a runtime speedup of up to $21 \times$ and an overall reduction in node count of at least $15 \%$ compared to state-of-the-art synthesis methods.

In electronic design automation, logic optimization operators play a crucial role in minimizing the gate count of logic circuits. However, their computation demands are high. Operators such as refactor conventionally form iterative cuts for each node, striving for a more compact representation - a task which often fails $98 \%$ on average. Prior research has sought to mitigate computational cost through parallelization. In contrast, our approach leverages a classifier to prune unsuccessful cuts preemptively, thus eliminating unnecessary resynthesis operations. Experiments on the refactor operator using the EPFL benchmark suite and 10 large industrial designs demonstrate that this technique can speedup logic optimization by $3.9 \times$ on average compared with the state-of-the-art ABC implementation.

Timing optimization during the global placement of integrated circuits has been a significant focus for decades, yet it remains a complex, unresolved issue. Recent analytical methods typically use pin-level timing information to adjust net weights, which is fast and simple but neglects the path-based nature of the timing graph. The existing path-based methods, however, cannot balance the accuracy and efficiency due to the exponential growth of number of critical paths. In this work, we propose a GPU-accelerated timing-driven global placement framework, integrating accurate path-level information into the efficient DREAMPlace infrastructure. It optimizes the fine-grained pin-to-pin attraction objective and is facilitated by efficient critical path extraction. We also design a quadratic distance loss function specifically to align with the RC timing model. Experimental results demonstrate that our method significantly outperforms the current leading timing-driven placers, achieving an average improvement of 40.5% in total negative slack (TNS) and 8.3% in worst negative slack (WNS), as well as an improvement in half-perimeter wirelength (HPWL).

Peephole optimization is commonly used in And-Inverter Graphs (AIGs) optimization algorithms. The efficiency of these algorithms heavily relies on the enumeration process of sub-structures. One common sub-structure is the cut, known for its efficient enumeration method and single-output characteristic. However, an increasing number of optimization algorithms now target sub-structures that incorporate multiple outputs. In this paper, we explore Maximum Fanout-Free Windows (MFFWs), a novel sub-structure with a multi-output nature, as well as its practical applications and enumeration algorithms. To accommodate various algorithm execution processes, we propose two different enumeration styles: Dynamic and Static. The Dynamic approach provides flexibility in adapting to changes in the AIG structure, whereas the Static method ensures efficiency as long as the AIG structure remains unchanged during execution. We apply these methods to rewriting and technology mapping to improve their runtime performance. Experimental results on pure enumeration and practical scenarios show the scalability and efficiency of the proposed MFFW enumeration methods.

Implementing Boolean functions with circuits consisting of logic gates is fundamental in digital computer design. However, the implemented circuit must be exactly equivalent, which hinders generative neural approaches on this task due to their occasionally wrong predictions. In this study, we introduce a generative neural model, the “Circuit Transformer”, which eliminates such wrong predictions and produces logic circuits strictly equivalent to given Boolean functions. The main idea is a carefully designed decoding mechanism that builds a circuit step-by-step by generating tokens, which has beneficial “cutoff properties” that block a candidate token once it invalidate equivalence. In such a way, the proposed model works similar to typical LLMs while logical equivalence is strictly preserved. A Markov decision process formulation is also proposed for optimizing certain objectives of circuits. Experimentally, we trained an 88-million-parameter Circuit Transformer to generate equivalent yet more compact forms of input circuits, outperforming existing neural approaches on both synthetic and real world benchmarks, without any violation of equivalence constraints. Code: https://github.com/snowkylin/circuit-transformer

Node Anomaly Detection (NAD) has gained significant attention in the deep learning community due to its diverse applications in real-world scenarios. Existing NAD methods primarily embed graphs within a single Euclidean space, while overlooking the potential of non-Euclidean spaces. Besides, to address the prevalent issue of limited supervision in real NAD tasks, previous methods tend to leverage synthetic data to collect auxiliary information, which is not an effective solution as shown in our experiments. To overcome these challenges, we introduce a novel SpaceGNN model designed for NAD tasks with extremely limited labels. Specifically, we provide deeper insights into a task-relevant framework by empirically analyzing the benefits of different spaces for node representations, based on which, we design a Learnable Space Projection function that effectively encodes nodes into suitable spaces. Besides, we introduce the concept of weighted homogeneity, which we empirically and theoretically validate as an effective coefficient during information propagation. This concept inspires the design of the Distance Aware Propagation module. Furthermore, we propose the Multiple Space Ensemble module, which extracts comprehensive information for NAD under conditions of extremely limited supervision. Our findings indicate that this module is more beneficial than data augmentation techniques for NAD. Extensive experiments conducted on 9 real datasets confirm the superiority of SpaceGNN, which outperforms the best rival by an average of 8.55% in AUC and 4.31% in F1 scores. Our code is available at https://github.com/xydong127/SpaceGNN.

The efficiency of Logic Optimization (LO) has become one of the key bottlenecks in chip design. To prompt efficient LO, previous studies propose using a key scoring function to predict and prune a large number of ineffective nodes of the LO heuristics. However, the existing scoring functions struggle to balance inference efficiency, interpretability, and generalization performance, which severely hinders their application to modern LO tools. To address this challenge, we propose a novel data-driven circuit symbolic learning framework, namely CMO, to learn lightweight, interpretable, and generalizable scoring functions. The major challenge of developing CMO is to discover symbolic functions that can well generalize to unseen circuits, i.e., the circuit symbolic generalization problem. Thus, the major technical contribution of CMO is the novel Graph Enhanced Symbolic Discovery framework, which distills dark knowledge from a well-designed Graph Neural Network (GNN) to enhance the generalization capability of the learned symbolic functions. To the best of our knowledge, CMO is *the first* graph-enhanced approach for discovering lightweight and interpretable symbolic functions that can well generalize to unseen circuits in LO. Experiments on three challenging circuit benchmarks show that the *interpretable* symbolic functions learned by CMO outperform previous state-of-the-art (SOTA) GPU-based and human-designed approaches in terms of *inference efficiency* and *generalization capability*. Moreover, we integrate CMO with the Mfs2 heuristic---one of the most time-consuming LO heuristics. The empirical results demonstrate that CMO significantly improves its efficiency while keeping comparable optimization performance when executed on a CPU-based machine, achieving up to 2.5× faster runtime.

Machine learning techniques have shown great potential in enhancing macro placement, a critical stage in modern chip design. However, existing methods primarily focus on *online* optimization of *intermediate surrogate metrics* that are available at the current placement stage, rather than directly targeting the *cross-stage metrics*---such as the timing performance---that measure the final chip quality. This is mainly because of the high computational costs associated with performing post-placement stages for evaluating such metrics, making the *online* optimization impractical. Consequently, these optimizations struggle to align with actual performance improvements and can even lead to severe manufacturing issues. To bridge this gap, we propose **LaMPlace**, which **L**earns **a** **M**ask for optimizing cross-stage metrics in macro placement. Specifically, LaMPlace trains a predictor on *offline* data to estimate these *cross-stage metrics* and then leverages the predictor to quickly generate a mask, i.e., a pixel-level feature map that quantifies the impact of placing a macro in each chip grid location on the design metrics. This mask essentially acts as a fast evaluator, enabling placement decisions based on *cross-stage metrics* rather than *intermediate surrogate metrics*. Experiments on commonly used benchmarks demonstrate that LaMPlace significantly improves the chip quality across several key design metrics, achieving an average improvement of 9.6\%, notably 43.0\% and 30.4\% in terms of WNS and TNS, respectively, which are two crucial cross-stage metrics that reflect the final chip quality in terms of the timing performance.

The widespread deployment of pre-trained language models (PLMs) has exposed them to textual backdoor attacks, particularly those planted during the pre-training stage. These attacks pose significant risks to high-reliability applications, as they can stealthily affect multiple downstream tasks. While certifying robustness against such threats is crucial, existing defenses struggle with the high-dimensional, interdependent nature of textual data and the lack of access to original poisoned pre-training data. To address these challenges, we introduce **F**uzzed **R**andomized **S**moothing (**FRS**), a novel approach for efficiently certifying language model robustness against backdoor attacks. FRS integrates software robustness certification techniques with biphased model parameter smoothing, employing Monte Carlo tree search for proactive fuzzing to identify vulnerable textual segments within the Damerau-Levenshtein space. This allows for targeted and efficient text randomization, while eliminating the need for access to poisoned training data during model smoothing. Our theoretical analysis demonstrates that FRS achieves a broader certified robustness radius compared to existing methods. Extensive experiments across various datasets, model configurations, and attack strategies validate FRS's superiority in terms of defense efficiency, accuracy, and robustness.

Neural Combinatorial Optimization (NCO) methods have exhibited promising performance in solving Vehicle Routing Problems (VRPs). However, most NCO methods rely on the conventional self-attention mechanism that induces excessive computational complexity, thereby struggling to contend with large-scale VRPs and hindering their practical applicability. In this paper, we propose a lightweight cross-attention mechanism with linear complexity, by which a Transformer network is developed to learn efficient and favorable solutions for large-scale VRPs. We also propose a Self-Improved Training (SIT) algorithm that enables direct model training on large-scale VRP instances, bypassing extensive computational overhead for attaining labels. By iterating solution reconstruction, the Transformer network itself can generate improved partial solutions as pseudo-labels to guide the model training. Experimental results on the Travelling Salesman Problem (TSP) and the Capacitated Vehicle Routing Problem (CVRP) with up to 100K nodes indicate that our method consistently achieves superior performance for synthetic and real-world benchmarks, significantly boosting the scalability of NCO methods.

Optimizing computing circuits such as multipliers and adders is a fundamental challenge in modern integrated circuit design. Recent efforts propose formulating this optimization problem as a reinforcement learning (RL) proxy task, offering a promising approach to search high-speed and area-efficient circuit design solutions. However, we show that the RL-based formulation (proxy task) converges to a local optimal design solution (original task) due to the deceptive reward signals and incrementally localized actions in the RL-based formulation. To address this challenge, we propose a novel model-based circuit genetic evolution (MUTE) framework, which reformulates the problem as a genetic evolution process by proposing a grid-based genetic representation of design solutions. This novel formulation avoids misleading rewards by evaluating and improving generated solutions using the true objective value rather than proxy rewards. To promote globally diverse exploration, MUTE proposes a multi-granularity genetic crossover operator that recombines design substructures at varying column ranges between two grid-based genetic solutions. To the best of our knowledge, MUTE is the first to reformulate the problem as a circuit genetic evolution process, which enables effectively searching for global optimal design solutions. We evaluate MUTE on several fundamental computing circuits, including multipliers, adders, and multiply-accumulate circuits. Experiments on these circuits demonstrate that MUTE significantly Pareto-dominates state-of-the-art approaches in terms of both area and delay. Moreover, experiments demonstrate that circuits designed by MUTE well generalize to large-scale computation-intensive circuits as well.

Recent advancements have significantly enhanced the performance of large language models (LLMs) in tackling complex reasoning tasks, achieving notable success in domains like mathematical and logical reasoning. However, these methods encounter challenges with complex planning tasks, primarily due to extended reasoning steps, diverse constraints, and the challenge of handling multiple distinct sub-tasks. To address these challenges, we propose HyperTree Planning (HTP), a novel reasoning paradigm that constructs hypertree-structured planning outlines for effective planning. The hypertree structure enables LLMs to engage in hierarchical thinking by flexibly employing the divide-and-conquer strategy, effectively breaking down intricate reasoning steps, accommodating diverse constraints, and managing multiple distinct sub-tasks in a well-organized manner. We further introduce an autonomous planning framework that completes the planning process by iteratively refining and expanding the hypertree-structured planning outlines. Experiments demonstrate the effectiveness of HTP, achieving state-of-the-art accuracy on the TravelPlanner benchmark with Gemini-1.5-Pro, resulting in a 3.6$\times$ performance improvement over o1-preview.

KV cache quantization can improve Large Language Models (LLMs) inference throughput and latency in long contexts and large batch-size scenarios while preserving LLMs effectiveness. However, current methods have three unsolved issues: overlooking layer-wise sensitivity to KV cache quantization, high overhead of online fine-grained decision-making, and low flexibility to different LLMs and constraints. Therefore, we theoretically analyze the inherent correlation of layer-wise transformer attention patterns to KV cache quantization errors and study why key cache is generally more important than value cache for quantization error reduction. We further propose a simple yet effective framework KVTuner to adaptively search for the optimal hardware-friendly layer-wise KV quantization precision pairs for coarse-grained KV cache with multi-objective optimization and directly utilize the offline searched configurations during online inference. To reduce the computational cost of offline calibration, we utilize the intra-layer KV precision pair pruning and inter-layer clustering to reduce the search space. Experimental results show that we can achieve nearly lossless 3.25-bit mixed precision KV cache quantization for LLMs like Llama-3.1-8B-Instruct and 4.0-bit for sensitive models like Qwen2.5-7B-Instruct on mathematical reasoning tasks. The maximum inference throughput can be improved by 21.25% compared with KIVI-KV8 quantization over various context lengths. Our code and searched configurations are available at https://github.com/cmd2001/KVTuner.

Tree-search-based reasoning methods have significantly enhanced the reasoning capability of large language models (LLMs) by facilitating the exploration of multiple intermediate reasoning steps, i.e., thoughts. However, these methods suffer from substantial inference latency, as they have to generate numerous reasoning thoughts, severely limiting LLM applicability. To address this challenge, we propose a novel Speculative Search (SpecSearch) framework that significantly accelerates LLM reasoning by optimizing thought generation. Specifically, SpecSearch utilizes a small model to strategically collaborate with a large model at both thought and token levels, efficiently generating high-quality reasoning thoughts. The major pillar of SpecSearch is a novel quality-preserving rejection mechanism, which effectively filters out thoughts whose quality falls below that of the large model's outputs. Moreover, we show that SpecSearch preserves comparable reasoning quality to the large model. Experiments on both the Qwen and Llama models demonstrate that SpecSearch significantly outperforms state-of-the-art approaches, achieving up to 2.12$\times$ speedup with comparable reasoning quality.

Logic synthesis is a crucial phase in the circuit design process, responsible for transforming hardware description language (HDL) designs into optimized netlists. However, traditional logic synthesis methods are computationally intensive, restricting their iterative use in refining chip designs. Recent advancements in large language models (LLMs), particularly those fine-tuned on programming languages, present a promising alternative. This work proposes augmenting LLMs with predictor networks trained to estimate circuit quality directly from HDL code. To enhance performance, the model is regularized using embeddings from graph neural networks (GNNs) trained on Look-Up Table (LUT) graphs, thereby incorporating lower-level circuit insights. The proposed method demonstrates superior performance compared to existing graph-based RTL-level estimation techniques on the established benchmark OpenABCD, while providing instant feedback on HDL code quality.

By virtue of its great utility in solving real-world problems, optimization modeling has been widely employed for optimal decision-making across various sectors, but it requires substantial expertise from operations research professionals. With the advent of large language models (LLMs), new opportunities have emerged to automate the procedure of mathematical modeling. This survey presents a comprehensive and timely review of recent advancements that cover the entire technical stack, including data synthesis and fine-tuning for the base model, inference frameworks, benchmark datasets, and performance evaluation. In addition, we conducted an in-depth analysis on the quality of benchmark datasets, which was found to have a surprisingly high error rate. We cleaned the datasets and constructed a new leaderboard with fair performance evaluation in terms of base LLM model and datasets. We also build an online portal that integrates resources of cleaned datasets, code and paper repository to benefit the community. Finally, we identify limitations in current methodologies and outline future research opportunities.

Key-Value (KV) cache eviction---which retains the KV pairs of the most important tokens while discarding less important ones---is a critical technique for optimizing both memory usage and inference latency in large language models (LLMs). However, existing approaches often rely on simple heuristics---such as attention weights---to measure token importance, overlooking the spatial relationships between token value states in the vector space. This often leads to suboptimal token selections and thus performance degradation. To tackle this problem, we propose a novel method, namely **AnDPro** (**An**chor **D**irection **Pro**jection), which introduces a projection-based scoring function to more accurately measure token importance. Specifically, AnDPro operates in the space of value vectors and leverages the projections of these vectors onto an *``Anchor Direction''*---the direction of the pre-eviction output---to measure token importance and guide more accurate token selection. Experiments on $16$ datasets from the LongBench benchmark demonstrate that AnDPro can maintain $96.07\\%$ of the full cache accuracy using only $3.44\\%$ KV cache budget, reducing KV cache budget size by $46.0\\%$ without compromising quality compared to previous state-of-the-arts.

Post-training compression has been a widely employed approach to scale down large language model (LLM) and facilitate efficient inference. In various proposed compression methods, including pruning and quantization, calibration data plays a vital role by informing the weight importance and activation dynamic ranges. However, how calibration data impacts the LLM capability after compression is less explored. Few of the existing works, though recognizing the significance of this study, only investigate the language modeling or commonsense reasoning performance degradation from limited angles, like the data sources or sample amounts. More systematic research is still needed to examine the impacts on different LLM capabilities in terms of compositional properties and domain correspondence of calibration data. In this work, we aim at bridging this gap and further analyze underlying influencing mechanisms from the activation pattern perspective. Especially, we explore the calibration data's impacts on high-level complex reasoning capabilities, like math problem solving and code generation. Delving into the underlying mechanism, we find that the representativeness and diversity in activation space more fundamentally determine the quality of calibration data. Finally, we propose a calibration data curation framework based on such observations and analysis, enhancing the performance of existing post-training compression methods on preserving critical LLM capabilities. Our code is provided in [Link](https://github.com/BokwaiHo/COLA.git).

Floorplanning is the initial step in the physical design process of Electronic Design Automation (EDA), directly influencing subsequent placement, routing, and final power of the chip. However, the solution space in floorplanning is vast, and current algorithms often struggle to explore it sufficiently, making them prone to getting trapped in local optima. To achieve efficient floorplanning, we propose **CORE**, a general and effective solution optimization framework that synergizes Evolutionary Algorithms (EAs) and Reinforcement Learning (RL) for high-quality layout search and optimization. Specifically, we propose the Clustering-based Diversified Evolutionary Search that directly perturbs layouts and evolves them based on novelty and performance. Additionally, we model the floorplanning problem as a sequential decision problem with B*-Tree representation and employ RL for efficient learning. To efficiently coordinate EAs and RL, we propose the reinforcement-driven mechanism and evolution-guided mechanism. The former accelerates population evolution through RL, while the latter guides RL learning through EAs. The experimental results on the MCNC and GSRC benchmarks demonstrate that CORE outperforms other strong baselines in terms of wirelength and area utilization metrics, achieving a 12.9\% improvement in wirelength. CORE represents the first evolutionary reinforcement learning (ERL) algorithm for floorplanning, surpassing existing RL-based methods. The code is available at https://github.com/yeshenpy/CORE.

Chip placement is a critical step in the Electronic Design Automation (EDA) workflow, which aims to arrange chip modules on the canvas to optimize the performance, power, and area (PPA) metrics of final designs.Recent advances show great potential of AI-based algorithms in chip placement.However, due to the lengthy EDA workflow, evaluations of these algorithms often focus on intermediate surrogate metrics, which are computationally efficient but often misalign with the final end-to-end performance (i.e., the final design PPA).To address this challenge, we propose to build ChiPBench, a comprehensive benchmark specifically designed to evaluate the effectiveness of AI-based algorithms in final design PPA metrics.Specifically, we generate a diverse evaluation dataset from $20$ circuits across various domains, such as CPUs, GPUs, and NPUs.We then evaluate six state-of-the-art AI-based chip placement algorithms on the dataset and conduct a thorough analysis of their placement behavior.Extensive experiments show that AI-based chip placement algorithms produce unsatisfactory final PPA results, highlighting the significant influence of often-overlooked factors like regularity and dataflow.We believe ChiPBench will effectively bridge the gap between academia and industry.

Large language models (LLMs) often produce reasoning steps that are superficially coherent yet internally inconsistent, leading to unreliable outputs. Since such failures typically arise from implicit or poorly-grounded knowledge, we introduce \emph{Grounded Reasoning in Dependency (GRiD)}, a novel dependency-aware reasoning framework that explicitly grounds reasoning steps in structured knowledge. GRiD represents reasoning as a graph consisting of interconnected knowledge extraction nodes and reasoning nodes, enforcing logical consistency through explicit dependencies. Each reasoning step is validated via a lightweight, step-wise verifier that ensures logical correctness relative to its premises. Extensive experiments across diverse reasoning benchmarks—including StrategyQA, CommonsenseQA, GPQA, and TruthfulQA—demonstrate that GRiD substantially improves reasoning accuracy, consistency, and faithfulness compared to recent state-of-the-art structured reasoning methods. Notably, GRiD enhances performance even when applied purely as a lightweight verification module at inference time, underscoring its generalizability and practical utility. Code is available at: https://github.com/cure-lab/GRiD.

Arithmetic circuit optimization remains a fundamental challenge in modern integrated circuit design. Recent advances have cast this problem within the Learning to Optimize (L2O) paradigm, where intelligent agents autonomously explore high-performance design spaces with encouraging results. However, existing approaches predominantly target coarse-grained architectural configurations, while the crucial interconnect optimization stage is often relegated to oversimplified proxy models or a heuristic approach. This disconnect undermines design quality, leading to suboptimal solutions in the circuit topology search space. To bridge this gap, we present **Arith-DAS**, a **D**ifferentiable **A**rchitecture **S**earch framework for **Arith**metic circuits. To the best of our knowledge, **Arith-DAS** is the first to formulate interconnect optimization within arithmetic circuits as a differentiable edge prediction problem over a multi-relational directed acyclic graph, enabling fine-grained, proxy-free optimization at the interconnection level. We evaluate **Arith-DAS** on a suite of representative arithmetic circuits, including multipliers and multiply-accumulate units. Experiments show substantial improvements over state-of-the-art L2O and conventional methods, achieving up to $\textbf{27.05}$% gain in hypervolume of area-delay Pareto front, a standard metric for evaluating multi-objective optimization performance. Moreover, integrating our optimized arithmetic units into large-scale AI accelerators yields up to $\textbf{6.59}$% delay reduction, demonstrating both scalability and real-world applicability.

With the development of large language models (LLMs), efficient inference through Key-Value (KV) cache compression has attracted considerable attention, especially for long-context generation. To compress the KV cache, recent methods identify critical KV tokens through static modeling of attention scores. However, these methods often struggle to accurately determine critical tokens as they neglect the *temporal patterns* in attention scores, resulting in a noticeable degradation in LLM performance. To address this challenge, we propose **AttentionPredictor**, which is the **first learning-based method to directly predict attention patterns for KV cache compression and critical token identification**. Specifically, AttentionPredictor learns a lightweight, unified convolution model to dynamically capture spatiotemporal patterns and predict the next-token attention scores. An appealing feature of AttentionPredictor is that it accurately predicts the attention score and shares the unified prediction model, which consumes negligible memory, among all transformer layers. Moreover, we propose a cross-token critical cache prefetching framework that hides the token estimation time overhead to accelerate the decoding stage. By retaining most of the attention information, AttentionPredictor achieves **13$\times$** KV cache compression and **5.6$\times$** speedup in a cache offloading scenario with comparable LLM performance, significantly outperforming the state-of-the-arts. The code is available at https://github.com/MIRALab-USTC/LLM-AttentionPredictor.

The smoothing issue in graph learning leads to indistinguishable node representations, posing significant challenges for graph-related tasks. However, our experiments reveal that this problem can uncover underlying properties of node anomaly detection (NAD) that previous research has missed. We introduce Individual Smoothing Patterns (ISP) and Neighborhood Smoothing Patterns (NSP), which indicate that the representations of anomalous nodes are harder to smooth than those of normal ones. In addition, we explore the theoretical implications of these patterns, demonstrating the potential benefits of ISP and NSP for NAD tasks. Motivated by these findings, we propose SmoothGNN, a novel unsupervised NAD framework. First, we design a learning component to explicitly capture ISP for detecting node anomalies. Second, we design a spectral graph neural network to implicitly learn ISP to enhance detection. Third, we design an effective coefficient based on our findings that NSP can serve as coefficients for node representations, aiding in the identification of anomalous nodes. Furthermore, we devise a novel anomaly measure to calculate loss functions and anomalous scores for nodes, reflecting the properties of NAD using ISP and NSP. Extensive experiments on 9 real datasets show that SmoothGNN outperforms the best rival by an average of 14.66% in AUC and 7.28% in Average Precision, with 75x running time speedup, validating the effectiveness and efficiency of our framework. Our code is available at https://github.com/xydong127/SmoothGNN.

Multiple patterning lithography (MPL) has been introduced in the integrated circuits manufacturing industry to enhance feature density as the technology node advances. A crucial step of MPL is assigning layout features to different masks, namely layout decomposition. Exact algorithms like integer linear programming (ILP) can solve layout decomposition to optimality but lack scalability for dense patterns. Relaxation algorithms (e.g., linear programming and semi-definite programming) and heuristics (e.g., exact cover) are capable of handling large cases at the cost of inferior solution quality. These methods rely on different mathematical solvers and expert-designed heuristics to offer a balance between solution quality and computational efficiency. In this article, we propose a unified layout decomposition framework comprising three algorithms: 1) satisfiability (SAT)-exact; 2) SAT-bilevel; and 3) SAT-fast, all leveraging the capabilities of Boolean SAT solvers. The SAT-exact ensures optimality, but with faster convergence than ILP, SAT-bilevel addresses the decomposition as a bilevel optimization problem for rapid near-optimal solutions, and SAT-fast handles very large layouts in an incremental manner. Experimental results demonstrate our framework’s superiority over existing state-of-the-art methods in terms of solution quality and runtime.

Lookup-table (LUT) mapping has been extensively utilized in logic synthesis, including being an indispensable step in FPGA design, serving as a building block in high-effort synthesis flows, and providing an algorithmic framework for logic optimization. Hence, a fast mapping algorithm is vital to satisfying the demand for synthesizing high-quality, large-scale modern VLSI designs. This article proposes two efficient GPU-parallel algorithms, namely LUT mapping and and-inverter graph (AIG) optimization using a precomputed database, which rely on a common parallel mapping framework that consists of novel fine-grained parallel mapping passes with high degree of parallelism. The mapping pass is enhanced by specifically tailored cut evaluation and memory management methods for GPUs that enable fast mapping of large circuits with limited GPU memory. Parallel timing analysis passes and parallel cut expansion passes are also proposed for constructing a fully GPU-accelerated LUT mapping flow. The core of parallel AIG optimization is a plugin of the mapping framework, which contains a self-adaptive parallel candidate structure evaluation procedure with high time efficiency and low hardware resource usage. Experiments show that on average, GPU LUT mapping and AIG optimization achieve$34.6\times $and$99.9\times $speedup with similar result quality, compared with the high-performance LUT mapper and AIG optimization algorithm with a database implemented in ABC, respectively, on large benchmarks. When combining the two algorithms with other GPU logic optimization algorithms, a GPU-based sequence targeting LUT network synthesis achieves$46.7\times $speedup with 4.7% smaller area and 0.2% smaller delay over ABC.

Many combinatorial multiobjective optimization problems involve very costly-to-evaluate objectives and constraints. It is very difficult, if not impossible, for traditional heuristics to solve these problems with an acceptable amount of computational time. In this paper, we show that offline machine learning can be very useful to assist multiobjective evolutionary algorithms to tackle this kind of problem. We take a complicated real-life multiobjective routing-packing problem as the test bed. We propose to use offline machine learning methods to replace time-consuming packing heuristics for packing feasibility prediction. Experiments show that the machine learning models can be 1,000 times faster than some commonly used packing heuristics and their accuracy can be as high as 98%. We adopt MOEA/D to decompose the problem into a number of single objective subproblems and solve them in a collaborative manner. We propose an encoding strategy to represent each routing scheme and use genetic operators to generate new routes. Experimental studies have been conducted on 100 instances from HUAWEI’s real-world logistics application and two test suites from the literature. Our proposed method can solve each HUAWEI instance in around one minute. Our solutions on the two test suites are comparable to other existing algorithms, and the overall computational cost of our method is significantly lower than others.

In the domain of chip design, hardware description languages (HDLs) play a pivotal role. However, due to the inherent complexity of HDLs and the scarcity of high-quality debugging resources, HDL bug fixing remains a challenging and time-consuming task, even for seasoned engineers. Consequently, there is a pressing need to develop automated HDL code debugging models, which can alleviate the burden on hardware engineers. Despite the strong capabilities of large language models (LLMs) in generating, completing, and debugging software code, their utilization in the specialized field of HDL debugging has been limited and, to date, has not yielded satisfactory results. In this paper, we propose an LLM-assisted HDL debugging framework, namely HDLdebugger, which consists of HDL debugging data generation via a reverse engineering approach, a search engine for retrieval-augmented generation, and a retrieval-augmented LLM fine-tuning approach. Through the integration of these components, HDLdebugger can automate and streamline HDL debugging for chip design. Our comprehensive experiments, conducted on an HDL code dataset sourced from Industry, reveal that HDLdebugger outperforms 13 cutting-edge LLM baselines, displaying exceptional effectiveness in HDL code debugging.

Representation learning over dynamic graphs is critical for many real-world applications such as social network services and recommender systems. Temporal graph neural networks (T-GNNs) are powerful representation learning methods and have demonstrated remarkable effectiveness on continuous-time dynamic graphs. However, T-GNNs still suffer from high time complexity, which increases linearly with the number of timestamps and grows exponentially with the model depth, making them not scalable to large dynamic graphs. To address the limitations, we propose Orca , a novel framework that accelerates T-GNN training by caching and reusing intermediate embeddings. We design an optimal caching policy, named MRD , for the uniform cache replacement problem, where embeddings at different intermediate layers have identical dimensions and recomputation costs. MRD not only improves the efficiency of training T-GNNs by maximizing the number of cache hits but also reduces the approximation errors by avoiding keeping and reusing extremely stale embeddings. For the general cache replacement problem, where embeddings at different intermediate layers can have different dimensions and recomputation costs, we solve this NP-hard problem by presenting a novel two-stage framework with approximation guarantees on the achieved benefit of caching. Furthermore, we have developed profound theoretical analyses of the approximation errors introduced by reusing intermediate embeddings, providing a thorough understanding of the impact of our caching and reuse schemes on model outputs. We also offer rigorous convergence guarantees for model training, adding to the reliability and validity of our Orca framework. Extensive experiments have validated that Orca can obtain two orders of magnitude speedup over state-of-the-art T-GNNs while achieving higher precision on various dynamic graphs.

Pre-routing timing prediction has been recently studied for evaluating the quality of a candidate cell placement in chip design. It involves directly estimating the timing metrics for both pin-level (slack, slew) and edge-level (net delay, cell delay), without time-consuming routing. However, it often suffers from signal decay and error accumulation due to the long timing paths in large-scale industrial circuits. To address these challenges, we propose a two-stage approach. First, we propose global circuit training to pre-train a graph auto-encoder that learns the global graph embedding from circuit netlist. Second, we use a novel node updating scheme for message passing on GCN, following the topological sorting sequence of the learned graph embedding and circuit graph. This scheme residually models the local time delay between two adjacent pins in the updating sequence, and extracts the lookup table information inside each cell via a new attention mechanism. To handle large-scale circuits efficiently, we introduce an order preserving partition scheme that reduces memory consumption while maintaining the topological dependencies. Experiments on 21 real world circuits achieve a new SOTA R2 of 0.93 for slack prediction, which is significantly surpasses 0.59 by previous SOTA method. Code will be available at: https://github.com/Thinklab-SJTU/EDA-AI.

Lookup-table (LUT) mapping is an indispensable step in FPGA design flows, and also serves as a building block in many technology-independent optimization algorithms. Therefore, it is crucial to accelerate LUT mapping in order to satisfy the demand for synthesizing high-quality, large-scale VLSI designs. Previous work on GPU LUT mapping suffers from low speedup due to limited degree of parallelism. In this paper, we propose an ultra-fast GPU-parallel LUT mapping engine named FineMap, which is composed of a novel fine-grained mapping phase with a high degree of parallelism, a parallel cut expansion phase and a parallel timing analysis pass. The mapping phase is enhanced by specifically tailored cut evaluation and memory management algorithms for GPUs that enable fast mapping of large circuits with limited GPU memory. Experiments show that compared with the high-performance mapper implemented in ABC, FineMap achieves 128.7× speedup with better quality in terms of area on large benchmarks.

Modern SAT solvers depend on conflict-driven clause learning to avoid recurring conflicts. Deleting less valuable learned clauses is a crucial component of modern SAT solvers to ensure efficiency. However, a single clause deletion policy cannot guarantee optimal performance on all SAT instances. This paper introduces a new clause deletion metric to diversify existing clause deletion policies. Then, we propose to use machine learning to evaluate and select clause deletion policies adaptively based on the input instance. We show that our method can reduce the runtime of the state-of-the-art SAT solver Kissat by 5.8% on large industry benchmarks.

Formal verification of integer multipliers is a significant but time-consuming problem. This paper introduces a novel approach that emphasizes the acceleration of symbolic computer algebra (SCA)-based verification systems from the perspective of efficient implementation instead of traditional algorithm enhancement. Our first strategy involves leveraging parallel computing to accelerate the rewriting process of the Gröbner basis. Confronting the issue of frequent memory operations during the Gröbner basis reduction phase, we propose a double buffering scheme coupled with an operator scheduler to minimize memory allocation and deallocation. These unique contributions are integrated into a state-of-the-art verification tool and result in substantial improvements in verification speed, demonstrating more than 15× speedup for a 1024×1024 multiplier.

Modern boolean satisfiability (SAT) solvers heavily rely on the conflict-driven clause learning (CDCL) framework to efficiently search the solution space and resolve conflicts during the search process. However, CDCL still faces challenges in terms of searching efficiency, particularly in complex cases with deep/symmetric/tree-based structures. To address this issue, numerous learning-driven methods have been proposed. However, these methods primarily focus on utilizing data-driven approaches to enhance searching efficiency and decision accuracy, while overlooking the core issue of the state explosion within the CDCL framework itself when the search starts at the wrong point. In this paper, we introduce DiffSAT, a novel approach that differentiates the discrete SAT problem and progressively searches for satisfying assignments through the forward and backward propagation of a neural network layer. DiffSAT initiates with an initial assignment obtained through semidefinite approximation and iteratively explores the solution space guided by a differential loss function. Notably, DiffSAT does not require training data and can be applied to large-scale problems that have not been seen before. The experimental results provide evidence that DiffSAT exhibits superior performance compared to existing end-to-end learning-based SAT solvers and can be generalized to solve large-scale SAT problems. Additionally, DiffSAT surpasses state-of-the-art SAT solvers in effectively finding satisfying assignments for complex problems in SATCOMP-2023.

As an early step in physical design, floorplanning plays a pivotal role in determining the performance upper bounds for downstream tasks and greatly impacts the PPA (power, performance, area) of the system. Efforts in floorplanning usually simplify modules as rectangles; however, assumptions of rectangular modules are not necessary for modern floorplan designs but could restrict floorplan solutions, typically resulting in lower chip area utilization with whitespace or overlaps among modules. In this paper, we challenge the widely accepted fixed-outline floorplanning problem setting which could lead to an inherent trade-off between whitespace and overlaps. We introduce JigsawPlanner, a novel and flexible Jigsaw-like floorPlanner that facilitates floorplanning to handle complex-shaped rectilinear modules. Given a global floorplan solution derived from an analytical method, we obtain the central positions of each module. Subsequently, we respectively partition the chip and modules into multiple grids and submodules, and assign these submodules to the grids using hierarchical Jonker-Volgenant algorithms and Cellular Automata. Empirical evaluations on public datasets show that JigsawPlanner can effectively eliminate white-space and overlaps simultaneously and significantly reduce the Half Perimeter Wire Length (HPWL) by an average of 10.50% compared to state-of-the-art baselines.

Register Transfer Level (RTL) code optimization is crucial for enhancing the efficiency and performance of digital circuits during early synthesis stages. Currently, optimization relies heavily on manual efforts by skilled engineers, often requiring multiple iterations based on synthesis feedback. In contrast, existing compiler-based methods fall short in addressing complex designs. This paper introduces RTLRewriter, an innovative framework that leverages large models to optimize RTL code. A circuit partition pipeline is utilized for fast synthesis and efficient rewriting. A multi-modal program analysis is proposed to incorporate vital visual diagram information as optimization cues. A specialized search engine is designed to identify useful optimization guides, algorithms, and code snippets that enhance the model's ability to generate optimized RTL. Additionally, we introduce a Cost-aware Monte Carlo Tree Search (C-MCTS) algorithm for efficient rewriting, managing diverse retrieved contents and steering the rewriting results. Furthermore, a fast verification pipeline is proposed to reduce verification cost. To cater to the needs of both industry and academia, we propose two benchmarking suites: the long Rewriter benchmark, targeting complex scenarios with extensive circuit partitioning, optimization trade-offs, and verification challenges, and the short Rewriter benchmark, designed for a wider range of scenarios and patterns. Our comparative analysis with established compilers such as Yosys and E-graph demonstrates significant improvements, highlighting the benefits of integrating large models into the early stages of circuit design. We provide our benchmarks at https://github.com/yaoxufeng/RTLRewriter-Bench.

For enterprise storage systems, users' directory/file and IO access traces are critical for fine-tuning and new designs. However, once these systems are deployed, only trace features with small sizes are allowed to be sent back to vendors. Therefore, it is crucial to develop effective techniques for highly compressed feature extraction and feature-based high-fidelity trace regeneration. Existing works primarily focus on I/O trace modeling and regeneration without considering the directory/file access information. In this paper, we propose a new technique, called Sketcher, that can sketch massive traces into highly compressed “joint features” with both directory/file and I/O characteristics, and then based on these features regenerate high-fidelity traces with a learning-based approach. For trace feature extraction, one key idea is to divide traces into multiple distance-associated segments, where each segment contains all files and IO accesses operating under the same directory and the differences between segments are represented as displacement of segment inside the directory tree. A dynamic weight scaling technique is proposed to further compress features considering feature criticality and the size quota, thereby achieving high compression ratios with critical characteristics (e.g., abnormal IO access patterns). For trace regeneration, a new learning-based RNN model is proposed to regenerate high-fidelity traces from extracted features based on sampling directory trees. We have implemented a fully functional prototype based on typical enterprise storage systems and evaluated Sketcher with real applications and benchmarks on Huawei OceanStor Dorado storage server. Results show that Sketcher can effectively extract features with marginal runtime overheads while achieving compression ratios up to 15.2K and regenerating high-fidelity traces.

Heuristics are widely used for dealing with complex search and optimization problems. However, manual design of heuristics can be often very labour extensive and requires rich working experience and knowledge. This paper proposes Evolution of Heuristic (EoH), a novel evolutionary paradigm that leverages both Large Language Models (LLMs) and Evolutionary Computation (EC) methods for Automatic Heuristic Design (AHD). EoH represents the ideas of heuristics in natural language, termed thoughts. They are then translated into executable codes by LLMs. The evolution of both thoughts and codes in an evolutionary search framework makes it very effective and efficient for generating high-performance heuristics. Experiments on three widely studied combinatorial optimization benchmark problems demonstrate that EoH outperforms commonly used handcrafted heuristics and other recent AHD methods including FunSearch. Particularly, the heuristic produced by EoH with a low computational budget (in terms of the number of queries to LLMs) significantly outperforms widely-used human hand-crafted baseline algorithms for the online bin packing problem.

Macro placement is a crucial step in modern chip design, and reinforcement learning (RL) has recently emerged as a promising technique for improving the placement quality. However, existing RL-based techniques are hindered by their low sample efficiency, requiring numerous online rollouts or substantial offline expert data to achieve bootstrap, which are often impractical in industrial scenarios. To address this challenge, we propose a novel sample-efficient framework, namely **EfficientPlace**, for fast macro placement. EfficientPlace integrates a global tree search algorithm to strategically direct the optimization process, as well as a RL agent for local policy learning to advance the tree search. Experiments on commonly used benchmarks demonstrate that EfficientPlace achieves remarkable placement quality within a short timeframe, outperforming recent state-of-the-art approaches.

Due to the growing complexity of modern Integrated Circuits (ICs), there is a need for automated circuit design methods. Recent years have seen increasing research in hardware design language generation to facilitate the design process. In this work, we propose a Verilog generation framework, BetterV, which fine-tunes large language models (LLMs) on processed domain-specific datasets and incorporates generative discriminators for guidance on particular design demands. Verilog modules are collected, filtered, and processed from the internet to form a clean and abundant dataset. Instruct-tuning methods are specially designed to fine-tune the LLMs to understand knowledge about Verilog. Furthermore, data are augmented to enrich the training set and are also used to train a generative discriminator on particular downstream tasks, providing guidance for the LLMs to optimize Verilog implementation. BetterV has the ability to generate syntactically and functionally correct Verilog, outperforming GPT-4 on the VerilogEval benchmark. With the help of task-specific generative discriminators, BetterV achieves remarkable improvements on various electronic design automation (EDA) downstream tasks, including netlist node reduction for synthesis and verification runtime reduction with Boolean Satisfiability (SAT) solving.

Logic Synthesis (LS) plays a vital role in chip design. A key task in LS is to simplify circuits---modeled by directed acyclic graphs (DAGs)---with functionality-equivalent transformations. To tackle this task, many LS heuristics apply transformations to subgraphs---rooted at each node on an input DAG---sequentially. However, we found that a large number of transformations are ineffective, which makes applying these heuristics highly time-consuming. In particular, we notice that the runtime of the Resub and Mfs2 heuristics often dominates the overall runtime of LS optimization processes. To address this challenge, we propose a novel data-driven LS heuristic paradigm, namely PruneX, to reduce ineffective transformations. The major challenge of developing PruneX is to learn models that well generalize to unseen circuits, i.e., the out-of-distribution (OOD) generalization problem. Thus, the major technical contribution of PruneX is the novel circuit domain generalization framework, which learns domain-invariant representations based on the transformation-invariant domain-knowledge. To the best of our knowledge, PruneX is the first approach to tackle the OOD problem in LS heuristics. We integrate PruneX with the aforementioned Resub and Mfs2 heuristics. Experiments demonstrate that PruneX significantly improves their efficiency while keeping comparable optimization performance on industrial and very large-scale circuits, achieving up to $3.1\times$ faster runtime.

Multiplier design—which aims to explore a large combinatorial design space to simultaneously optimize multiple conflicting objectives—is a fundamental problem in the integrated circuits industry. Although traditional approaches tackle the multi-objective multiplier optimization problem by manually designed heuristics, reinforcement learning (RL) offers a promising approach to discover high-speed and area-efficient multipliers. However, the existing RL-based methods struggle to find Pareto-optimal circuit designs for all possible preferences, i.e., weights over objectives, in a sample-efficient manner. To address this challenge, we propose a novel hierarchical adaptive (HAVE) multi-task reinforcement learning framework. The hierarchical framework consists of a meta-agent to generate diverse multiplier preferences, and an adaptive multi-task agent to collaboratively optimize multipliers conditioned on the dynamic preferences given by the meta-agent. To the best of our knowledge, HAVE is the first to well approximate Pareto-optimal circuit designs for the entire preference space with high sample efficiency. Experiments on multipliers across a wide range of input widths demonstrate that HAVE significantly Pareto-dominates state-of-the-art approaches, achieving up to 28% larger hypervolume. Moreover, experiments demonstrate that multipliers designed by HAVE can well generalize to large-scale computation-intensive circuits.

The min-max vehicle routing problem (min-max VRP) traverses all given customers by assigning several routes and aims to minimize the length of the longest route. Recently, reinforcement learning (RL)-based sequential planning methods have exhibited advantages in solving efficiency and optimality. However, these methods fail to exploit the problem-specific properties in learning representations, resulting in less effective features for decoding optimal routes. This paper considers the sequential planning process of min-max VRPs as two coupled optimization tasks: customer partition for different routes and customer navigation in each route (i.e., partition and navigation). To effectively process min-max VRP instances, we present a novel attention-based Partition-and-Navigation encoder (P&N Encoder) that learns distinct embeddings for partition and navigation. Furthermore, we utilize an inherent symmetry in decoding routes and develop an effective agent-permutation-symmetric (APS) loss function. Experimental results demonstrate that the proposed Decoupling-Partition-Navigation (DPN) method significantly surpasses existing learning-based methods in both single-depot and multi-depot min-max VRPs. Our code is available at

Vehicle routing problems (VRP) are very important in many realworld applications and has been studied for several decades.Recently, neural combinatorial optimization (NCO) has attracted growing research effort.NCO is to train a neural network model to solve an optimization problem in question.However, existing NCO methods often build a different model for each routing problem, which significantly hinders their application in some areas where there are many different VRP variants to solve.In this work, we make a first attempt to tackle the crucial challenge of cross-problem generalization in NCO.We formulate VRPs as different combinations of a set of shared underlying attributes and solve them simultaneously via a single model through attribute composition.In this way, our proposed model can successfully solve VRPs with unseen attribute combinations in a zero-shot generalization manner.In our experiments, the neural model is trained on five VRP variants and its performance is tested on eleven VRP variants.The experimental results show that the model demonstrates superior performance on these eleven VRP variants, reducing the average gap to around 5% from over 20% and achieving a notable performance boost on both benchmark datasets and real-world logistics scenarios.

Boolean satisfiability (SAT) problems are routinely solved by SAT solvers in real-life applications, yet solving time can vary drastically between solvers for the same instance.This has motivated research into machine learning models that can predict, for a given SAT instance, which solver to select among several options.Existing SAT solver selection methods all rely on some hand-picked instance features, which are costly to compute and ignore the structural information in SAT graphs.In this paper we present GraSS, a novel approach for automatic SAT solver selection based on tripartite graph representations of instances and a heterogeneous graph neural network (GNN) model.While GNNs have been previously adopted in other SAT-related tasks, they do not incorporate any domain-specific knowledge and ignore the runtime variation introduced by different clause orders.We enrich the graph representation with domain-specific decisions, such as novel node feature design, positional encodings for clauses in the graph, a GNN architecture tailored to our tripartite graphs and a runtime-sensitive loss function.Through extensive experiments, we demonstrate that this combination of raw representations and domain-specific choices leads to improvements in runtime for a pool of seven state-of-theart solvers on both an industrial circuit design benchmark, and

Logic Synthesis (LS) aims to generate an optimized logic circuit satisfying a given functionality, which generally consists of circuit translation and optimization. It is a challenging and fundamental combinatorial optimization problem in integrated circuit design. Traditional LS approaches rely on manually designed heuristics to tackle the LS task, while machine learning recently offers a promising approach towards next-generation logic synthesis by neural circuit generation and optimization. In this paper, we first revisit the application of differentiable neural architecture search (DNAS) methods to circuit generation and found from extensive experiments that existing DNAS methods struggle to exactly generate circuits, scale poorly to large circuits, and exhibit high sensitivity to hyper-parameters. Then we provide three major insights for these challenges from extensive empirical analysis: 1) DNAS tends to overfit to too many skip-connections, consequently wasting a significant portion of the network's expressive capabilities; 2) DNAS suffers from the structure bias between the network architecture and the circuit inherent structure, leading to inefficient search; 3) the learning difficulty of different input-output examples varies significantly, leading to severely imbalanced learning. To address these challenges in a systematic way, we propose a novel regularized triangle-shaped circuit network generation framework, which leverages our key insights for completely accurate and scalable circuit generation. Furthermore, we propose an evolutionary algorithm assisted by reinforcement learning agent restarting technique for efficient and effective neural circuit optimization. Extensive experiments on four different circuit benchmarks demonstrate that our method can precisely generate circuits with up to 1200 nodes. Moreover, our synthesized circuits significantly outperform the state-of-the-art results from several competitive winners in IWLS 2022 and 2023 competitions.

Single-stage neural combinatorial optimization solvers have achieved near-optimal results on various small-scale combinatorial optimization (CO) problems without requiring expert knowledge. However, these solvers exhibit significant performance degradation when applied to large-scale CO problems. Recently, two-stage neural methods motivated by divide-and-conquer strategies have shown efficiency in addressing large-scale CO problems. Nevertheless, the performance of these methods highly relies on problem-specific heuristics in either the dividing or the conquering procedure, which limits their applicability to general CO problems. Moreover, these methods employ separate training schemes and ignore the interdependencies between the dividing and conquering strategies, often leading to sub-optimal solutions. To tackle these drawbacks, this article develops a unified neural divide-and-conquer framework (i.e., UDC) for solving general large-scale CO problems. UDC offers a Divide-Conquer-Reunion (DCR) training method to eliminate the negative impact of a sub-optimal dividing policy. Employing a high-efficiency Graph Neural Network (GNN) for global instance dividing and a fixed-length sub-path solver for conquering divided sub-problems, the proposed UDC framework demonstrates extensive applicability, achieving superior performance in 10 representative large-scale CO problems. The code is available at https://github.com/CIAM-Group/NCO_code/tree/main/single_objective/UDC-Large-scale-CO-master

In the Integrated Circuit (IC) design flow, floorplanning (FP) determines the position and shape of each block. Serving as a prototype for downstream tasks, it is critical and establishes the upper bound of the final PPA (Power, Performance, Area). However, with the emergence of 3D IC with stacked layers, existing methods are not flexible enough to handle the versatile constraints. Besides, they typically face difficulties in aligning the cross-die modules in 3D ICs due to their heuristic representations, which could potentially result in severe data transfer failures. To address these issues, we propose FlexPlanner, a flexible learning-based method in hybrid action space with multi-modality representation to simultaneously handle position, aspect ratio, and alignment of blocks. To our best knowledge, FlexPlanner is the first learning-based approach to discard heuristic-based search in the 3D FP task. Thus, the solution space is not limited by the heuristic floorplanning representation, allowing for significant improvements in both wirelength and alignment scores. Specifically, FlexPlanner models 3D FP based on multi-modalities, including vision, graph, and sequence. To address the non-trivial heuristic-dependent issue, we design a sophisticated policy network with hybrid action space and asynchronous layer decision mechanism that allow for determining the versatile properties of each block. Experiments on public benchmarks MCNC and GSRC show the effectiveness. We significantly improve the alignment score from 0.474 to 0.940 and achieve an average reduction of 16% in wirelength. Moreover, our method also demonstrates zero-shot transferability on unseen circuits.

Abstract Within the electronic design automation (EDA) domain, artificial intelligence (AI)-driven solutions have emerged as formidable tools, yet they typically augment rather than redefine existing methodologies. These solutions often repurpose deep learning models from other domains, such as vision, text, and graph analytics, applying them to circuit design without tailoring to the unique complexities of electronic circuits. Such an “AI4EDA” approach falls short of achieving a holistic design synthesis and understanding, overlooking the intricate interplay of electrical, logical, and physical facets of circuit data. This study argues for a paradigm shift from AI4EDA towards AI-rooted EDA from the ground up, integrating AI at the core of the design process. Pivotal to this vision is the development of a multimodal circuit representation learning technique, poised to provide a comprehensive understanding by harmonizing and extracting insights from varied data sources, such as functional specifications, register-transfer level (RTL) designs, circuit netlists, and physical layouts. We champion the creation of large circuit models (LCMs) that are inherently multimodal, crafted to decode and express the rich semantics and structures of circuit data, thus fostering more resilient, efficient, and inventive design methodologies. Embracing this AI-rooted philosophy, we foresee a trajectory that transcends the current innovation plateau in EDA, igniting a profound “shift-left” in electronic design methodology. The envisioned advancements herald not just an evolution of existing EDA tools but a revolution, giving rise to novel instruments of design-tools that promise to radically enhance design productivity and inaugurate a new epoch where the optimization of circuit performance, power, and area (PPA) is achieved not incrementally, but through leaps that redefine the benchmarks of electronic systems’ capabilities.

Cutting planes (cuts) play an important role in solving mixed-integer linear programs (MILPs), which formulate many important real-world applications. Cut selection heavily depends on (P1) which cuts to prefer and (P2) how many cuts to select. Although modern MILP solvers tackle (P1)-(P2) by human-designed heuristics, machine learning carries the potential to learn more effective heuristics. However, many existing learning-based methods learn which cuts to prefer, neglecting the importance of learning how many cuts to select. Moreover, we observe that (P3) what order of selected cuts to prefer significantly impacts the efficiency of MILP solvers as well. To address these challenges, we propose a novel hierarchical sequence/set model (HEM) to learn cut selection policies. Specifically, HEM is a bi-level model: (1) a higher-level module that learns how many cuts to select, (2) and a lower-level module-that formulates the cut selection as a sequence/set to sequence learning problem-to learn policies selecting an ordered subset with the cardinality determined by the higher-level module. To the best of our knowledge, HEM is the first data-driven methodology that well tackles (P1)-(P3) simultaneously. Experiments demonstrate that HEM significantly improves the efficiency of solving MILPs on eleven challenging MILP benchmarks, including two Huawei's real problems.

Technology mapping quality heavily depends on the subject graph structure. To overcome structural biases, operators construct choice nodes to enable mappings with improved node and level counts. Nevertheless, state-of-the-art structural choice operators scale poorly with graph size.We present the lightweight structural choices (LCH) operator that incorporates equivalencies by processing only subparts of the graph. We propose multiple heuristics that rely on specific node extraction orders and subpart sizes to extract non-overlapping components. Compared to state-of-the-art methods on EPFL circuits, LCH is 2.35x faster enduring a small sacrifice in node count (3%) and level reduction (2%).

Multiple patterning lithography (MPL) has been introduced in the integrated circuits manufacturing industry to enhance feature density as the technology node advances. A crucial step of MPL is assigning layout features to different masks, namely layout decomposition. Exact algorithms like integer linear programming (ILP) can solve layout decomposition to optimality but lacks scalability for very dense patterns. Approximation algorithms (e.g., linear programming, semi-definite programming) and heuristics (e.g., Exact-Cover) are capable of handling large cases but can only get inferior solutions. In this paper, we propose a new exact algorithm that tackles layout decomposition by solving a series of boolean satisfiability instances. Our algorithm can preserve optimality and achieve more than 4× speedup compared to ILP. In addition, we provide an approximation algorithm by reformulating the layout decomposition to a bilevel optimization problem. Experiments show that our approximation algorithm can attain higher solution quality compared to SDP and heuristics within faster convergence.

Rewriting is a widely used logic optimization approach incorporated in most commercial logic synthesis tools. In this paper, we present a new rewriting method based on And-Inverted Graph (AIG). Rather than focusing on cut rewriting, it considers a novel sub-structure called Maximum Fanout-Free Window (MFFW) and rewrites with a more compact implementation. Both exact synthesis and heuristic methods can be adopted to optimize MFFWs. A database dependent framework is proposed to store the optimal sub-structures to accelerate the processing. We further propose the semi-canonicalization to reduce the scale of the database, which could reduce more than 98% of the 4-input MFFW database. Extensive experiments on benchmark datasets demonstrate both the effectiveness and efficiency of our proposed framework.

Logic synthesis tools synthesize circuit structures to optimize specific targets given reasonable constraints and runtime using a set of well-defined operators. The efficiency of these operators is critical to achieving better runtime and optimization convergence. However, most synthesis operators are designed heuristically with fixed and sub-optimal traversal orders of nodes, cuts, and candidate subgraphs that are independent of circuit structures and functionalities. This leads to redundant computation and loss of optimization opportunities. Due to the spatial structure similarity, sub-circuits already synthesized in the same circuit contain meaningful information to guide more efficient synthesis for unvisited sub-circuits. Historical evaluation and gain features can learn from conflicts and be utilized to predict synthesis gain and prune invalid sub-circuits. Instead of using high-weight feature extraction and models, we utilize efficient prediction models with lightweight structural and functional features to reduce overhead. We thus propose a generalizable and dynamic scoring and pruning framework EffiSyn to accelerate logic synthesis operators while maintaining synthesis effectiveness. For example, we further improve the highly optimized operator drw by scoring and pruning invalid cuts and precomputed subgraphs. Extensive experiments on 20 public and industrial circuits validate that EffiSyn can accelerate drw by about 35% with negligible effectiveness loss or even with effectiveness improvement. Experiments over diverse circuits and synthesis sequences also validate the generalization of the proposed framework.

This paper introduces SATformer, a novel Transformer-based approach for the Boolean Satisfiability (SAT) problem. Rather than solving the problem directly, SATformer approaches the problem from the opposite direction by focusing on unsatisfiability. Specifically, it models clause interactions to identify any unsatisfiable sub-problems. Using a graph neural network, we convert clauses into clause embeddings and employ a hierarchical Transformer-based model to understand clause correlation. SATformer is trained through a multi-task learning approach, using the single-bit satisfiability result and the minimal unsatisfiable core (MUC) for UNSAT problems as clause supervision. As an end-to-end learning-based satisfiability classifier, the performance of SATformer surpasses that of NeuroSAT significantly. Furthermore, we integrate the clause predictions made by SATformer into modern heuristic-based SAT solvers and validate our approach with a logic equivalence checking task. Experimental results show that our SATformer can decrease the runtime of existing solvers by an average of 21.33%.

Circuit representation learning aims to obtain neural repre-sentations of circuit elements and has emerged as a promising research direction that can be applied to various EDA and logic reasoning tasks. Existing solutions, such as DeepGate, have the potential to embed both circuit structural information and functional behavior. However, their capabilities are limited due to weak supervision or flawed model design, resulting in unsatisfactory performance in downstream tasks. In this paper, we introduce Deep Gate2, a novel functionality-aware learning framework that significantly improves upon the original DeepGate solution in terms of both learning effectiveness and efficiency. Our approach involves using pairwise truth table differences between sampled logic gates as training supervision, along with a well-designed and scalable loss function that explicitly considers circuit functionality. Additionally, we consider inherent circuit characteristics and design an efficient one-round graph neural network (GNN), resulting in an order of magnitude faster learning speed than the original DeepGate solution. Experimental results demonstrate significant improvements in two practical downstream tasks: logic synthesis and Boolean satisfiability solving. The code is available at https://github.com/cure-lablDeepGate2.

Technology mapping is a crucial step in the logic synthesis in chip design e.g. Field Programmable Gate Arrays (FPGAs) design, where a logic network is transformed into a K-bounded lookup tables (K-LUTs) network. Traditional mapping algorithms converges quickly to a suboptimal result, which limits the exploration capacity for further improvement. In this paper, we propose a new mapping method called Exploration-enhanced heuristics and Adaptive sequencing for Technology Mapping (EasyMap). EasyMap includes a pool of new heuristics and considers the mapping exploration as a conditional sequence optimization problem. During the mapping exploration procedure, heuristic algorithms with specific parameters are selected and applied sequentially. Our EasyMap outperforms the widely used IfMap in ABC by a significant margin. In particular, when optimizing area with a level constraint, EasyMap outperforms IfMap by reducing 9.1% more area on arithmetic circuits of the EPFL benchmark. Moreover, when optimizing area without level constraints at the same time, EasyMap can reduce 19% more area than IfMap on arithmetic circuits.

The microarchitecture design of processors faces growing complexity due to expanding design space and time-intensive verification processes. Utilizing historical design task data can improve the search process, but managing distribution discrepancies between different source tasks is essential for enhancing the search method's generalization ability. In light of this, we introduce IT-DSE, a microarchitecture searching framework with the surrogate model pre-trained to absorb knowledge from previous design tasks. The Feature Tokenizer-Transformer (FT-Transformer) serves as a backbone, facilitating feature extraction from source tasks even with varied design spaces. Concurrently, the invariant risk minimization (IRM) paradigm bolsters generalization ability under data distribution discrepancies. Further, IT-DSE exploits a combination of multi-objective Bayesian optimization and a model ensemble to discover Pareto-optimal designs Experimental results indicate that IT-DSE effectively harnesses the knowledge of existing microarchitecture designs and uncovers designs that outperform previous methods in terms of power, performance, and area (PPA).

Optimizing the quality of results (QoR) of a circuit during the logic synthesis (LS) phase in chip design is critical yet challenging. While most existing methods often mitigate the computational hardness by restricting the action space to a small set of operators and fixing the operator's parameters, they are susceptible to local minima and may not meet the high demand from industrial cases. In this paper, we develop a more comprehensive optimization approach via sample-efficient reinforcement learning (RL). Specifically, we first build a complete logic synthesis-RL environment, where the action space consists of three types of operators: logic optimization, technology mapping, and post-mapping, along with their associated continuouslbinary parameters for optimization as well. Based on this environment, we devise a hybrid proximal policy optimization (PPO) model to handle both discrete operators and parameters and design a distributed architecture to improve sample collection efficiency. Furthermore, we devise a dynamic exploration module to improve the exploration efficiency under the constraint of limited samples. We term our method as Exploration-enhanced RL for Logic Synthesis Sequence Optimization(EasySO). Results on the EPFL benchmark show that our method significantly outperforms current state-of-the-art models based on Bayesian optimization (BO) and the previous RL-based methods. Compared to resyn2, our EasySO achieves an average of 25.4% LUT-6 count optimization without sacrificing level values. Moreover, as of the time for this submission, we rank 26 first places among 40 optimization targets in the EPFL competition.

Data prefetching is important for storage system optimization and access performance improvement. Traditional prefetchers work well for mining access patterns of sequential logical block address (LBA) but cannot handle complex non-sequential patterns that commonly exist in real-world applications. The state-of-the-art (SOTA) learning-based prefetchers cover more LBA accesses. However, they do not adequately consider the spatial interdependencies between LBA deltas, which leads to limited performance and robustness. This paper proposes a novel Stream-Graph neural network-based Data Prefetcher (SGDP). Specifically, SGDP models LBA delta streams using a weighted directed graph structure to represent interactive relations among LBA deltas and further extracts hybrid features by graph neural networks for data prefetching. We conduct extensive experiments on eight real-world datasets. Empirical results verify that SGDP outperforms the SOTA methods in terms of the hit ratio by 6.21%, the effective prefetching ratio by 7.00%, and speeds up inference time by 3.13× on average. Besides, we generalize SGDP to different variants by different stream constructions, further expanding its application scenarios and demonstrating its robustness. SGDP offers a novel data prefetching solution and has been verified in commercial hybrid storage systems in the experimental phase. Our codes and appendix are available at https://github.com/yyysjz1997/SGDP/.

Industrial SAT formula generation is a critical yet challenging task. Existing SAT generation approaches can hardly simultaneously capture the global structural properties and maintain plausible computational hardness. We first present an in-depth analysis for the limitation of previous learning methods in reproducing the computational hardness of original instances, which may stem from the inherent homogeneity in their adopted split-merge procedure. On top of the observations that industrial formulae exhibit clear community structure and oversplit substructures lead to the difficulty in semantic formation of logical structures, we propose HardSATGEN, which introduces a fine-grained control mechanism to the neural split-merge paradigm for SAT formula generation to better recover the structural and computational properties of the industrial benchmarks. Experiments including evaluations on private and practical corporate testbed show the superiority of HardSATGEN being the only method to successfully augments formulae maintaining similar computational hardness and capturing the global structural properties simultaneously. Compared to the best previous methods, the average performance gains achieve 38.5% in structural statistics, 88.4% in computational metrics, and over 140.7% in the effectiveness of guiding solver tuning by our generated instances. Source code is available at https://github.com/Thinklab-SJTU/HardSATGEN.

Representation learning over dynamic graphs is critical for many real-world applications such as social network services and recommender systems. Temporal graph neural networks (T-GNNs) are powerful representation learning methods and have achieved remarkable effectiveness on continuous-time dynamic graphs. However, T-GNNs still suffer from high time complexity, which increases linearly with the number of timestamps and grows exponentially with the model depth, causing them not scalable to large dynamic graphs. To address the limitations, we propose Orca, a novel framework that accelerates T-GNN training by non-trivially caching and reusing intermediate embeddings. We design an optimal cache replacement algorithm, named MRU, under a practical cache limit. MRU not only improves the efficiency of training T-GNNs by maximizing the number of cache hits but also reduces the approximation errors by avoiding keeping and reusing extremely stale embeddings. Meanwhile, we develop profound theoretical analyses of the approximation error introduced by our reuse schemes and offer rigorous convergence guarantees. Extensive experiments have validated that Orca can obtain two orders of magnitude speedup over the state-of-the-art baselines while achieving higher precision on large dynamic graphs.

Temporal graph neural networks (T-GNNs) are state-of-the-art methods for learning representations over dynamic graphs. Despite the superior performance, T-GNNs still suffer from high computational complexity caused by the tedious recursive temporal message passing scheme, which hinders their applicability to large dynamic graphs. To address the problem, we build the theoretical connection between the temporal message passing scheme adopted by T-GNNs and the temporal random walk process on dynamic graphs. Our theoretical analysis indicates that it would be possible to select a few influential temporal neighbors to compute a target node's representation without compromising the predictive performance. Based on this finding, we propose to utilize T-PPR, a parameterized metric for estimating the influence score of nodes on evolving graphs. We further develop an efficient single-scan algorithm to answer the top- k T-PPR query with rigorous approximation guarantees. Finally, we present Zebra, a scalable framework that accelerates the computation of T-GNN by directly aggregating the features of the most prominent temporal neighbors returned by the top- k T-PPR query. Extensive experiments have validated that Zebra can be up to two orders of magnitude faster than the state-of-the-art T-GNNs while attaining better performance.

Due to the continuous advancement of semicon-ductor technologies, there are more defects than ever widely distributed in manufactured chips. In order to meet the high product quality and low defective-parts-per-million (DPPM) goals, Boolean Satisfiability (SAT) technique has been shown to be a robust alternative to conventional APTG techniques, especially for hard-to-detect faults. However, the SAT-based ATPG still confronts two challenges. The first one is to reduce extra computational overhead of SAT modeling, i.e. to transform a circuit testing problem to a Conjunctive Normal Form (CNF) which is the foundation of modern SAT solvers. The second one lies in the SAT solver's efficiency which is brought by the loss of structural information during CNF transformation. In this work, we propose a new SAT-based ATPG approach to address the two challenges mentioned above: (1) To reduce CNF transformation overhead, we utilize a simulation-driven pre-processing for narrowing down the fault propagation and activation logic cones, leading to an improvement in CNF transformation and reduction in runtime. (2) To further improve the solving efficiency, We propose new ranking-based heuristics to build more effective conflict database, enabling the direct solving for small scale instance and a looking-head method for large scale ones. Extensive experimental results on industrial circuits demonstrate that on average the proposed approach could cover 89.67% of the faults failed by a commercial ATPG tool with a comparable runtime.

Recently, many models show their superiority in sequence and parameter tuning. However, they usually generate non-deterministic flows and require lots of training data. We thus propose a heuristic and iterative flow, namely HIMap, for deterministic logic synthesis. In which, domain knowledge of the functionality and parameters of synthesis operators and their correlations to netlist PPA is fully utilized to design synthesis templates for various objetives. We also introduce deterministic and effective heuristics to tune the templates with relatively fixed operator combinations and iteratively improve netlist PPA. Two nested iterations with local searching and early stopping can thus generate dynamic sequence for various circuits and reduce runtime. HIMap improves 13 best results of the EPFL combinational benchmarks for delay (5 for area). Especially, for several arithmetic benchmarks, HIMap significantly reduces LUT-6 levels by 11.6 ~ 21.2% and delay after P&R by 5.0 ~ 12.9%.

Cache plays an important role to maintain high and stable performance (i.e. high throughput, low tail latency and throughput jitter) in storage systems. Existing rule-based cache management methods, coupled with engineers' manual configurations, cannot meet ever-growing requirements of both time-varying workloads and complex storage systems, leading to frequent cache overloading.

During the logic synthesis flow of EDA, a sequence of graph transformation operators are applied to the circuits so that the Quality of Results (QoR) of the circuits highly depends on the chosen operators and their specific parameters in the sequence, making the search space operator-dependent and increasingly exponential. In this paper, we formulate the logic synthesis design space exploration as a conditional sequence optimization problem, where at each transformation step, an optimization operator is selected and its corresponding parameters are decided. To solve this problem, we propose a novel sequential black-box optimization approach without human intervention: 1) Due to the conditional and sequential structure of operator sequence with variable length, we build an embedding alignment cells based recurrent neural network as a surrogate model to estimate the QoR of the logic synthesis flow with historical data. 2) With the surrogate model, we construct acquisition function to balance exploration and exploitation with respect to each metric of the QoR. 3) We use multi-objective optimization algorithm to find the Pareto front of the acquisition functions, along which a batch of sequences, consisting of parameterized operators, are (randomly) selected to users for evaluation under the budget of computing resource. We repeat the above three steps until convergence or time limit. Experimental results on public EPFL benchmarks demonstrate the superiority of our approach over the expert-crafted optimization flows and other machine learning based methods. Compared to resyn2, we achieve 11.8% LUT-6 count descent improvements without sacrificing level values.

Continued advances in process technology have led to a relentless increase in the design complexity of integrated circuits (ICs). In order to meet the increasing demand of low defective-parts-per-million (DPPM) and high product quality of the complex circuit designs, Boolean Satisfactory (SAT) has worked as a robust alternative to conventional APTG techniques. In SAT-based ATPG, logic cones related to the target faults are transformed to Boolean formulas, and standard SAT solving procedures are then used for solving these formulas. Recently, artificial intelligence (AI) techniques have shown great potential in speeding-up SAT solvers. However, the high diversity of the structural characteristics within the logic cones of target faults limits the AI techniques being used for SAT-based ATPG. To meet this challenge, this paper proposes a neural fault analysis technology that is made up of a multi-stage learning model and the testability classifier to highly increase the SAT-based ATPG solving efficiency. The multi-stage learning model is composed of a generative model with a topology structure discriminator and a conflict structure discriminator. It is trained for high-quality data synthesis. Then the testability classifier is trained for adaptive heuristic selection and effective initialization in SAT-based ATPG. Experimental results on both open-source and industrial circuits demonstrate that the neural fault analysis can reduce the SAT solving time by 34.79% and reduce the runtime of SAT-based ATPG by 7.43% on average. It is also shown that the proposed neural fault analysis can cover 9.14% of the faults failed by the conventional SAT-based ATPG framework with a comparable runtime.

Scheduling job flows efficiently and rapidly on distributed computing clusters is one of huge challenges for daily operation of data centers. In a practical scenario, a single job consists of numerous stages with complex dependency relation represented as a Directed Acyclic Graph (DAG) structure. Nowa-days a data center usually equips with a cluster of heterogeneous computing servers which are different in the hardware/software configuration. From both the cost saving and environmental friendliness, the data centers could benefit a lot from optimizing the job scheduling problems in the heterogeneous environment. Thus the problem has attracted more and more attention from both the industry and academy. In this paper, we propose a task-duplication based learning algorithm, namely LACHESIS22The second of the Three Fates in ancient Greek mythology, who deter-mines destiny., aiming to optimize the problem. In the proposed approach, it first perceives the topological dependencies between jobs using a reinforcement learning framework and a specially designed graph neural network (GNN) to select the most promising task to be executed. Then the task is assigned to a specific executor with the consideration of duplicating all its precedent tasks according to an expert-designed rules. We have conducted extensive experiments over standard workloads to evaluate the proposed solution. The experimental results suggest that LACHESIS can achieve at most 26.7% reduction of makespan and 35.2% improvement of speedup ratio over seven strong baseline algorithms, including the state-of-the-art heuristics methods and a variety of deep reinforcement learning based algorithms.

This work is geared toward a real-world manufacturing planning (MP) task, whose two objectives are to maximize the order fulfillment rate and minimize the total cost. More important, the requirements and constraints in real manufacturing make the MP task very challenging in several aspects. For example, the MP needs to cover many production components of multiple plants over a 30-day horizon, which means that it involves a large number of decision variables. Furthermore, the MP task's two objectives have extremely different magnitudes, and some constraints are difficult to handle. Facing these uncompromising practical requirements, we introduce an interactive multiobjective optimization-based MP system in this article. It can help the decision maker reach a satisfactory tradeoff between the two objectives without consuming massive calculations. In the MP system, the submitted MP task is modeled as a multiobjective integer programming (MOIP) problem. Then, the MOIP problem is addressed via a two-stage multiobjective optimization algorithm (TSMOA). To alleviate the heavy calculation burden, TSMOA transforms the optimization of the MOIP problem into the optimization of a series of single-objective problems (SOPs). Meanwhile, a new SOP solving strategy is used in the MP system to further reduce the computational cost. It utilizes two sequential easier SOPs as the approximator of the original complex SOP for optimization. As part of the MP system, TSMOA and the SOP solving strategy are demonstrated to be efficient in real-world MP applications. In addition, the effectiveness of TSMOA is also validated on benchmark problems. The results indicate that TSMOA as well as the MP system are promising.

Recent years have witnessed the fast growth in telecommunication (Telco) techniques from 2G to upcoming 5G. Precise outdoor localization is important for Telco operators to manage, operate and optimize Telco networks. Differing from GPS, Telco localization is a technique employed by Telco operators to localize outdoor mobile devices by using measurement report (MR) data. When given MR samples containing noisy signals (e.g., caused by Telco signal interference and attenuation), Telco localization often suffers from high errors. To this end, the main focus of this paper is how to improve Telco localization accuracy via the algorithms to detect and repair outlier positions with high errors. Specifically, we propose a context-aware Telco localization technique, namely${\sf RLoc}$, which consists of three main components: a machine-learning-based localization algorithm, a detection algorithm to find flawed samples, and a repair algorithm to replace outlier localization results by better ones (ideally ground truth positions). Unlike most existing works to detect and repair every flawed MR sample independently, we instead take into account spatio-temporal locality of MR locations and exploit trajectory context to detect and repair flawed positions. Our experiments on the real MR data sets from 2G GSM and 4G LTE Telco networks verify that our work${\sf RLoc}$can greatly improve Telco location accuracy. For example,${\sf RLoc}$on a large 4G MR data set can achieve 32.2 meters of median errors, around 17.4 percent better than state-of-the-art.

An algebraic modeling system (AMS) is a type of mathematical software for optimization problems, which allows users to define symbolic mathematical models in a specific language, instantiate them with given source of data, and solve them with the aid of external solver engines. With the bursting scale of business models and increasing need for timeliness, traditional AMSs are not sufficient to meet the following industry needs: 1) million-variable models need to be instantiated from raw data very efficiently; 2) Strictly feasible solution of million-variable models need to be delivered in a rapid manner to make up-to-date decisions against highly dynamic environments. Grassland is a rapid AMS that provides an end-to-end solution to tackle these emerged new challenges. It integrates a parallelized instantiation scheme for large-scale linear constraints, and a sequential decomposition method that accelerates model solving exponentially with an acceptable loss of optimality. Extensive benchmarks on both classical models and real enterprise scenario demonstrate 6-10x speedup of Grassland over state-of-the-art solutions on model instantiation. Our proposed system has been deployed in the large-scale real production planning scenario of Huawei. With the aid of our decomposition method, Grassland successfully accelerated Huawei's million-variable production planning simulation pipeline from hours to 3-5 minutes, supporting near-real-time production plan decision making against highly dynamic supply-demand environment.

The discovery and prediction of block access patterns in hybrid storage systems is of crucial importance for effective tier management. Existing methods are usually based on heuristics and unable to handle complex patterns. This work newly introduces transformer to block access pattern prediction. We remark that block accesses in the tier management systems are aggregated temporally and spatially as multivariate time series of block access frequency, so the runtime requirements are relaxed, making complex models applicable for the deployment. Moreover, enormous and rarely accessed blocks in storage systems and the structure of traditional transformer models would result in millions of redundant parameters and make them impractical to be deployed. We incorporate Tensor-Train Decomposition (TTD) with transformer and propose the Compressed Full Tenor Transformer (CFTT), in which all linear layers in the vanilla transformer are replaced with tensor-train layers. Weights of input and output layers are shared to further reduce parameters and reuse knowledge implicitly. CFTT can significantly reduce the model size and computation cost, which is critical to save storage space and inference time. Extensive experiments are conducted on synthetic and real-world datasets. The results demonstrate that transformers achieve state-of-the-art performance stably in terms of top-k hit rates. Moreover, the proposed CFTT compresses transformers 16× to 461× and speeds up inference 5× without sacrificing performance on the whole, which facilitates its applications in tier management in hybrid storage systems.

The 3-dimensional bin packing problem (3D-BPP) is not only fundamental in combinatorial optimization but also widely applied in real world logistics. In the modern logistics industry, the complexity of constraints, heterogeneity of cargoes and scale of orders are dramatically increased, leading to great challenges to devise packing plans up to standard. While the tree search algorithm is proved to be a successful paradigm to solve the 3D-BPP, it is too time-consuming to be applied in the aforementioned large-scale scenarios. To overcome the limitation, we propose a data-driven tree search algorithm (DDTS) to tackle the 3D-BPP. The solution space with complicated constraints is explored by a tree search algorithm, and a convolutional neural network trained with historical data guides pruning the tree so as to accelerate the search process. Computational experiments on real-world datasets show that our algorithm outperforms the state-of-the-art approach with a loading rate improvement of 2.47%. Moreover, the deep learning technique increases searching efficiency by 37.14% with only 0.04% performance loss. The algorithm has been deployed in Huawei Logistics System, which increases the loading rate by 3% and could reduce the logistics cost by millions of dollars per year. To the best of our knowledge, we are the first to embed pruning networks into tree search for the large-scale 3D-BPP.

The Dynamic Pickup and Delivery Problem (DPDP) is aimed at dynamically scheduling vehicles among multiple sites in order to minimize the cost when delivery orders are not known a priori. Although DPDP plays an important role in modern logistics and supply chain management, state-of-the-art DPDP algorithms are still limited on their solution quality and efficiency. In practice, they fail to provide a scalable solution as the numbers of vehicles and sites become large. In this paper, we propose a data-driven approach, Spatial-Temporal Aided Double Deep Graph Network (ST-DDGN), to solve industry-scale DPDP. In our method, the delivery demands are first forecast using spatial-temporal prediction method, which guides the neural network to perceive spatial-temporal distribution of delivery demand when dispatching vehicles. Besides, the relationships of individuals such as vehicles are modelled by establishing a graph-based value function. ST-DDGN incorporates attention-based graph embedding with Double DQN (DDQN). As such, it can make the inference across vehicles more efficiently compared with traditional methods. Our method is entirely data driven and thus adaptive, i.e., the relational representation of adjacent vehicles can be learned and corrected by ST-DDGN from data periodically. We have conducted extensive experiments over real-world data to evaluate our solution. The results show that ST-DDGN reduces 11.27% number of the used vehicles and decreases 13.12% total transportation cost on average over the strong baselines, including the heuristic algorithm deployed in our UAT (User Acceptance Test) environment and a variety of vanilla DRL methods. We are due to fully deploy our solution into our online logistics system and it is estimated that millions of USD logistics cost can be saved per year.

Hybrid Flow Shop Scheduling Problem (HFSP) is an essential problem in the automated warehouse scheduling, aiming at optimizing the sequence of jobs and the assignment of machines to utilize the makespan or other objectives. Existing algorithms adopt fixed search paradigm based on expert knowledge to seek satisfactory solutions. However, considering the varying data distribution and large scale of the practical HFSP, these methods fail to guarantee the quality of the obtained solution under the real-time requirement, especially facing extremely different data distribution. To address this challenge, we propose a novel Multi-Graph Attributed Reinforcement Learning based Optimization (MGRO) algorithm to better tackle the practical large-scale HFSP and improve the existing algorithm. Owing to incorporating the reinforcement learning-based policy search approach with classic search operators and the powerful multi-graph based representation, MGRO is capable of adjusting the search paradigm according to specific instances and enhancing the search efficiency. Specifically, we formulate the Gantt chart of the instance into the multi-graph-structured data. Then Graph Neural Network (GNN) and attention-based adaptive weighted pooling are employed to represent the state and make MGRO size-agnostic across arbitrary sizes of instances. In addition, a useful reward shaping approach is designed to facilitate model convergence. Extensive numerical experiments on both the publicly available dataset and real industrial dataset from Huawei Supply Chain Business Unit demonstrate the superiority of MGRO over existing baselines.

The Dynamic Pickup and Delivery Problem (DPDP) is an essential problem in the logistics domain, which is NP-hard. The objective is to dynamically schedule vehicles among multiple sites to serve the online generated orders such that the overall transportation cost could be minimized. The critical challenge of DPDP is the orders are not known a priori, i.e., the orders are dynamically generated in real-time. To address this problem, existing methods partition the overall DPDP into fixed-size sub-problems by caching online generated orders and solve each sub-problem, or on this basis to utilize the predicted future orders to optimize each sub-problem further. However, the solution quality and efficiency of these methods are unsatisfactory, especially when the problem scale is very large. In this paper, we propose a novel hierarchical optimization framework to better solve large-scale DPDPs. Specifically, we design an upper-level agent to dynamically partition the DPDP into a series of sub-problems with different scales to optimize vehicles routes towards globally better solutions. Besides, a lower-level agent is designed to efficiently solve each sub-problem by incorporating the strengths of classical operational research-based methods with reinforcement learning-based policies. To verify the effectiveness of the proposed framework, real historical data is collected from the order dispatching system of Huawei Supply Chain Business Unit and used to build a functional simulator. Extensive offline simulation and online testing conducted on the industrial order dispatching system justify the superior performance of our framework over existing baselines.

Computer systems such as storage systems normally require transparent white-box algorithms that are interpretable for human experts. In this work, we propose a learning-aided heuristic design method, which automatically generates human-readable strategies from Deep Reinforcement Learning (DRL) agents. This method benefits from the power of deep learning but avoids the shortcoming of its black-box property. Besides the white-box advantage, experiments in our storage production's resource allocation scenario also show that this solution outperforms the system's default settings and the elaborately handcrafted strategy by human experts.

The proliferation of telco networks and mobile terminals brings the accumulation of tremendous amounts of measure report(MR) data at a rapid pace. The MR data is generated by mobile objects while connecting to data services and is stored in backend data centers. To geo-tag or localize such MR data is believed to have a profound effect on the analytics and optimizations of telco and traffic networks. However, MR records are of noisy and partial observations regarding to mobile objects' geo-locations and hence pose challenges to accurate telco data localization. There have been quite a few attempts. Single-point localization methods map a MR record to a location, but come out with limited accuracies due to the ignorance of spatiotemporal coherence of successive MR records. Recent efforts on sequential localization techniques alleviate this by mapping a sequence of MR records to a trajectory. However, existing solutions are often with assumptions on specific models, e.g., mobility and signal strength distributions, or priori knowledge on topology space, e.g., road networks, limiting the deployment in practice. To this end, we propose a data-driven framework to tackle the challenges in sequential telco localization. We solely use raw MR records and a public third-party GPS dataset for the learning of the correlations between mobile objects' locations and MR records, requiring no model assumptions and priori knowledge. To handle the data-intensive workloads during the learning process, we use materialized views for efficient online localization and light-weighted indexing techniques for periodical parameters tuning, in order to improve the efficiency and scalability. Results on real data show that our solution achieves 58.8 percent improvement in median localization errors compared with state-of-art sequential localization techniques that require hypothesis models and priori knowledge, making our solution superior in terms of effectiveness, efficiency, and employability.

Telecommunication (Telco) outdoor position recovery aims to localize outdoor mobile devices by leveraging measurement report (MR) data. Unfortunately, Telco position recovery requires sufficient amount of MR samples across different areas and suffers from high data collection cost. For an area with scarce MR samples, it is hard to achieve good accuracy. In this paper, by leveraging the recently developed transfer learning techniques, we design a novel Telco position recovery framework, called TLoc, to transfer good models in the carefully selected source domains (those fine-grained small subareas) to a target one which originally suffers from poor localization accuracy. Specifically, TLoc introduces three dedicated components: 1) a new coordinate space to divide an area of interest into smaller domains, 2) a similarity measurement to select best source domains, and 3) an adaptation of an existing transfer learning approach. To the best of our knowledge, TLoc is the first framework that demonstrates the efficacy of applying transfer learning in the Telco outdoor position recovery. To exemplify, on the 2G GSM and 4G LTE MR datasets in Shanghai, TLoc outperforms a non-transfer approach by 27.58 and 26.12 percent less median errors, and further leads to 47.77 and 49.22 percent less median errors than a recent fingerprinting approach NBL.

This work proposes a novel approach for multiple time series forecasting. At first, multi-way delay embedding transform (MDT) is employed to represent time series as low-rank block Hankel tensors (BHT). Then, the higher-order tensors are projected to compressed core tensors by applying Tucker decomposition. At the same time, the generalized tensor Autoregressive Integrated Moving Average (ARIMA) is explicitly used on consecutive core tensors to predict future samples. In this manner, the proposed approach tactically incorporates the unique advantages of MDT tensorization (to exploit mutual correlations) and tensor ARIMA coupled with low-rank Tucker decomposition into a unified framework. This framework exploits the low-rank structure of block Hankel tensors in the embedded space and captures the intrinsic correlations among multiple TS, which thus can improve the forecasting results, especially for multiple short time series. Experiments conducted on three public datasets and two industrial datasets verify that the proposed BHT-ARIMA effectively improves forecasting accuracy and reduces computational cost compared with the state-of-the-art methods.

Selecting an appropriate model to forecast product demand is critical to the manufacturing industry. However, due to the data complexity, market uncertainty and users' demanding requirements for the model, it is challenging for demand analysts to select a proper model. Although existing model selection methods can reduce the manual burden to some extent, they often fail to present model performance details on individual products and reveal the potential risk of the selected model. This paper presents DFSeer, an interactive visualization system to conduct reliable model selection for demand forecasting based on the products with similar historical demand. It supports model comparison and selection with different levels of details. Besides, it shows the difference in model performance on similar products to reveal the risk of model selection and increase users' confidence in choosing a forecasting model. Two case studies and interviews with domain experts demonstrate the effectiveness and usability of DFSeer.

Production planning in the manufacturing industry is crucial for fully utilizing factory resources (e.g., machines, raw materials and workers) and reducing costs. With the advent of industry 4.0, plenty of data recording the status of factory resources have been collected and further involved in production planning, which brings an unprecedented opportunity to understand, evaluate and adjust complex production plans through a data-driven approach. However, developing a systematic analytics approach for production planning is challenging due to the large volume of production data, the complex dependency between products, and unexpected changes in the market and the plant. Previous studies only provide summarized results and fail to show details for comparative analysis of production plans. Besides, the rapid adjustment to the plan in the case of an unanticipated incident is also not supported. In this paper, we propose PlanningVis, a visual analytics system to support the exploration and comparison of production plans with three levels of details: a plan overview presenting the overall difference between plans, a product view visualizing various properties of individual products, and a production detail view displaying the product dependency and the daily production details in related factories. By integrating an automatic planning algorithm with interactive visual explorations, PlanningVis can facilitate the efficient optimization of daily production planning as well as support a quick response to unanticipated incidents in manufacturing. Two case studies with real-world data and carefully designed interviews with domain experts demonstrate the effectiveness and usability of PlanningVis.

Multivariate time series forecasting has wide applications such as traffic flow prediction, supermarket commodity demand forecasting and etc. In literature, Due to the complex temporal patterns and inter-dependencies among multivariate time series, a large number of forecasting models have been developed. However, one question still remains unclear: how these models perform on a certain forecasting task, and there is lack of comprehensive performance comparison of these models on different tasks. To this end, in this paper, we conduct a systematic evaluation of eight representative forecasting models over eight multivariate time series datasets, and have the following findings: 1) When the datasets exhibit strong periodic patterns, deep learning models perform best. Otherwise on the datasets in a non-periodic manner, the statistical models such as ARIMA perform best. 2) For the long term prediction involving a high horizon value, the direct prediction strategy could lead to lower errors than the recursive one, but at the cost of higher training time. 3) For the multivariate time series explicitly involving graphic inter-dependencies among the multivariates, e.g., the road network topology in the spatio-temporal time series of traffic volumes in multiple routes, the Graph Convolution Network can incorporate the graphic inter-dependencies into their forecasting models for smaller prediction errors.

Recent years have witnessed unprecedented amounts of telecommunication (Telco) data generated by Telco networks. For example, measurement records (MRs) are generated to report the connection states, e.g., received signal strength, between mobile devices and Telco networks. MR data have been widely used to precisely recover outdoor locations of mobile devices for the applications e.g., human mobility, urban planning and traffic forecasting. Existing works using first-order sequence models such as the Hidden Markov Model (HMM) attempt to capture the spatio-temporal locality in underlying mobility patterns for lower localization errors. Such HMM approaches typically assume stable mobility pattern of underlying mobile devices. Yet real MR datasets frequently exhibit heterogeneous mobility patterns due to mixed transportation modes of underlying mobile devices and uneven distribution of the positions associated with MR samples. To address this issue, we propose a deep neural network (DNN)-based position recovery framework, namely PRNet, which can ensemble the power of CNN, sequence model LSTM, and two attention mechanisms to learn local, short- and long-term spatio-temporal dependencies from input MR samples. Extensive evaluation on six datasets collected at three representative areas (core, urban, and suburban areas in Shanghai, China) indicates that PRNet greatly outperforms seven counterparts.

The bin packing problem is one of the most fundamental optimization problems. Owing to its hardness as a combinatorial optimization problem class and its wide range of applications in different domains, different variations of the problem are emerged and many heuristics have been proposed for obtaining approximate solutions.

Given a set of objects O (such as hotels), each can be represented as a point in a multi-dimensional feature space where each dimension corresponds to one attribute of the objects (such as price). Given the preference of a customer, the objects in O not dominated by any other object (i.e., beat in all dimensions) are those worthy to be further considered. Such objects are known as skyline objects in database community. Suppose we have an object o ∈ O. If o is a skyline point, other skyline objects are called peers of o. If o is not a skyline object, it must be dominated by some skyline objects which are called dominators of o. Given a large number of user preferences, an interesting problem is to identify the most frequent peer/dominator (MFP/MFD) of o. The MFP/MFD search has unique values in competitor analysis of various information systems. However, it is a challenging task because of the complexity to process a large number of user preferences. In this work, we provide robust solutions including exact and approximate methods. While the exact solutions explore the dominance relationship in the feature space, the approximate solutions are based on sampling techniques with theoretical bounds. We did extensive tests on large data sets which are up to 100 million user preferences generated from commercial surveys. The test resutls demonstrate the exact algorithms outperform various baseline algorithms significantly, and the approximate algorithms make further improvement by one order of magnitude with 90-98 percent accuracy.

Industrial telecommunication applications prefer to run at the optimal capacity configuration to achieve the required Quality of Service (QoS) at the minimum cost. The optimal capacity configuration is usually achieved through the selection of cell towers capacities and locations. Given a set of service providers (e.g., cell towers) and a set of customers (e.g., major residential areas), where each customer has an amount of demand and each provider has multiple candidate capacities and corresponding costs, the optimal capacity selection is configured through spatial matching to satisfy the demand of each customer at the minimum cost. However, existing solutions developed for spatial matching, in which each provider's capacity is fixed, cannot be directly applied to the capacity configuration problem with multiple capacities and location selections. In this paper, we are the first to study Service Provider Configuration and Planning with Optimal Spatial Matching (SPC-POSM) problem, in which the objectives are 1) to select the proper capacity for each provider at the minimum total cost and 2) to assign providers' service to satisfy the demand of each customer on a condition that the matching distance is no more than service quality requirement. We prove that SPC-POSM problem is NP-hard and design an efficient two-layer meta-heuristic framework to solve the problem. Unsupervised learning technique is designed to accelerate the calculation and a novel local search mechanism is embedded to further improve solution quality. Extensive experimental results on both real and synthetic datasets verify the effectiveness and efficiency of the proposed framework.

Split Delivery Vehicle Routing Problem with 3D Loading Constraints (3L-SDVRP) can be seen as the most important problem in large-scale manufacturing logistics. The goal is to devise a strategy consisting of three NP-hard planning components: vehicle routing, cargo splitting and container loading, which shall be jointly optimized for cost savings. The problem is an enhanced variant of the classical logistics problem 3L-CVRP, and its complexity leaps beyond current studies of solvability. Our solution employs a novel data-driven three-layer search algorithm (DTSA), which we designed to improve both the efficiency and effectiveness of traditional meta-heuristic approaches, through learning from data and from simulation.

Map-matching is an important preprocessing task for many location-based services (LBS). It projects each GPS point in trajectory data onto digital maps. The state of art work typically employed the Hidden Markov model (HMM) by shortest path computation. Such shortest path computation may not work very well for very low sampling rate trajectory data, leading to low matching precision and high running time. To solve this problem, this paper, we first identify the frequent patterns from historical trajectory data and next perform the map matching for higher precision and faster running time. Since the identified frequent patterns indicate the mobility behaviours for the majority of trajectories, the map matching thus has chance to satisfy the matching precision with high confidence. Moreover, the proposed FP-forest structure can greatly speedup the lookup of frequent paths and lead to high computation efficiency. Our experiments on real world data set validate that the proposed FP-matching outperforms state of arts in terms of effectiveness and efficiency.

In smart cities, green cellular networks play a crucial role to support wireless access for numerous devices anywhere and anytime with efficiency and sustainability. Because base stations (BSes) consume more than 70% of overall cellular network infrastructure energy, saving the power consumption of BSes is the key task to build a green cellular network. Except for low power design of the BS hardware and software, the traffic-driven BS sleeping operation is an economical way to improve existing cellular networks, which can reduce the BS power consumption at low traffic load. However, prior BS sleeping strategies establish on the static temporal characteristics of traffic load, which ignore the fact that network traffic is influenced by many factors such as time, human mobility, holiday, weather, etc. Hence, prior traffic estimation is coarse, and the BS sleeping strategies cannot apply to the changing network traffic. In this paper, we exploit a machine learning method to estimate the BS traffic and propose a BS sleeping strategy based on predicted traffic for power saving in the cellular network. We analyze network traffic in multi-views: temporal influence, spatial influence, and event influence. Then, we propose a multi-view ensemble learning model to predict network traffic load, which learns the traffic in multi-views and combine the results with ensemble. Furthermore, we formulate a BS sleeping strategy based on the predicted traffic load. Finally, we evaluate our traffic prediction algorithm on real cellular network data. The evaluation shows that our traffic prediction algorithm improves about 40% than state-of-the-art machine learning methods. Also, we evaluate the proposed BS sleeping strategy, which yields about 10% more energy savings and less device damage than the competitors in the simulated environment.

Telecommunication (Telco) localization is a technique to accurately locate mobile devices (MDs) using measurement report (MR) data, and has been widely used in Telco industry. Many techniques have been proposed, including measurement-based statistical algorithms, fingerprinting algorithms and different machine learning-based algorithms. However, it has not been well studied yet on how these algorithms perform on various Telco MR data sets. In this paper, we conduct a comprehensive experimental study of five state-of-art algorithms for Telco localization. Based on real data sets from two Telco networks, we study the localization performance of such algorithms. We find that a Random Forest-based machine learning algorithm performs best in most experiments due to high localization accuracy and insensitivity to data volume. The experimental result and observation in this paper may inspire and enhance future research in Telco localization.

Telecommunication (Telco) localization is a technique to localize mobile devices (MDs) outdoor by using measurement report (MR) data. Unfortunately, existing Telco localization approaches (with localization error > 50 meters) cannot achieve comparable localization accuracy as GPS (with localization error ±10 meters). In particular, due to signal interference and attenuation caused by high buildings in urban cities, it is hard to achieve high localization accuracy if MR records contain unstable signal data. To this end, we propose to first detect those MR records incurring high localization errors and next repair the predicted location (with high errors). Our experiments on two real MR data sets from 2G GSM and 4G LTE Telco networks verify that a Telco localization approach, enhanced by the proposed detection and repair algorithms, can greatly improve localization accuracy. For example, the enhancement algorithm on 2G and 4G data sets can achieve 29.5 and 13.2 meters of median errors, around 160.68% and 201.51% better than previous results. Such result indicates that our work can achieve nearly comparable localization accuracy as GPS.

Recent years witnessed popular use of various mobile devices, e.g., smart phones, vehicle networks and wearable watches. Such mobile devices generate massive trajectory data, and literature have proposed various algorithms to leverage the trajectory data for map inference. Unfortunately, such algorithms are hard to achieve both high map quality and computation efficiency. In this paper, we propose a solution framework to infer road network maps with high quality and efficiency. The key of our map inference is to divide map extent into smaller cells and maintain a binary cell-trajectory matrix. The binary matrix determines whether or not a trajectory passes a cell. We infer the importance of each cell from the matrix using a popular topic model (e.g., LDA [13] and pLSA [8]). Based on such computed importance, we next infer representative points and road segments to derive a road network map. Our extensive experiments on real data sets verify that the proposed inference algorithm can achieve higher map quality and meanwhile 1.5 ×, 6.8 × and 280 × shorter running time, when compared with three state of the arts including three representative work [4], [7], [14].

Urbanization's rapid progress has modernized a large number of human beings' lives. This urbanization progress is accompanied by the increase of a variety of shops (e.g., restaurants and fitness centers) to meet the increasing citizens, which means business opportunities for the investors. Nevertheless, it is difficult for the investors to catch such opportunities because opening what kind of business at which place is not easy to decide. In this paper, we take this challenge and define the business opportunity mining problem, which recommends new business categories at a partitioned business district. Specifically, we exploit the data from location-based social networks (LBSNs) to mine the business opportunities, guiding the business owners to open new commercial shops in certain categories at a particular area. First, we define the properties of a business district and propose a greedy algorithm to partition a city into different districts. Next, we propose an embedding model to learn latent representations of categories, which captures the functional correlations among business categories. Furthermore, we propose a ranking model based on the pairwise loss to recommend categories for a specific district. Finally, we conduct experiments on Yelp data, and experimental results show that our proposed method outperforms the baseline methods and resolves the problem well.

In this work, we focus on two fundamental questions that are unprecedentedly important to urban planners to understand the functional characteristics of various urban regions throughout a city, namely, (i) how to identify regional weather-traffic sensitivity index throughout a city, that indicates the degree to which the region traffic in a city is impacted by weather changes; (ii) among complex regional features, such as road structure and population density, how to dissect the most influential regional features that drive the urban region traffic to be more vulnerable to weather changes. However, these two questions are nontrivial to answer, because urban traffic changes dynamically over time and is essentially affected by many other factors, which may dominate the overall impact. We make the first study on these questions, by developing a weather-traffic index (WTI) system. The system includes two main components: weather-traffic index establishment and key factor analysis. Using the proposed system, we conducted comprehensive empirical study in Shanghai, and the weather-traffic indices extracted have been validated to be surprisingly consistent with real world observations. Further regional key factor analysis yields interesting results. For example, house age has significant impact on the weather-traffic index, which sheds light on future urban planning and reconstruction.

Collective behavior is an important concept defined to capture behavioral patterns emerged among the crowd spontaneously. In social science, people's behaviors can be regarded as temporal transitions between a set of typical states (e.g., home and work) which are always associated with certain locations. This fact leads to an interesting research topic in developing ways to explore people's collective behavior patterns through movement analysis, which is our focus in this paper. In recent years, massive volumes of spatiotemporal data generated by mobile phones, called telco data, bring an unprecedented opportunity to study collective behaviors in terms of large coverage and fine-grained resolution. However, distilling valuable collective behavior patterns from the large scale of telco data is not an easy task. The challenge is rooted in two aspects, including the data uncertainty as well as the lack of methods to characterize, compare and understand dynamic crowd behaviors, which triggers the use of visual analytics to take full advantage of machines' computational power as well as human's domain knowledge and cognitive abilities. In this paper, we propose TelcoFlow, a comprehensive visual analytics system which incorporates advanced quantitative analyses (e.g., statebased behavior model) and intuitive visualizations (e.g., an extended flow view embedded with state glyphs) to support an efficient and in-depth analysis of collective behaviors based on telco data. Case studies with a real-world dataset and expert interviews are carried out to demonstrate the effectiveness of our system for analysts to gain insights into collective behaviors and facilitate various analytical tasks.

Inference algorithms of latent Dirichlet allocation (LDA), either for small or big data, can be broadly categorized into expectation-maximization (EM), variational Bayes (VB) and collapsed Gibbs sampling (GS). Looking for a unified understanding of these different inference algorithms is currently an important open problem. In this paper, we revisit these three algorithms from the entropy perspective, and show that EM can achieve the best predictive perplexity (a standard performance metric for LDA accuracy) by minimizing directly the cross entropy between the observed word distribution and LDA's predictive distribution. Moreover, EM can change the entropy of LDA's predictive distribution through tuning priors of LDA, such as the Dirichlet hyperparameters and the number of topics, to minimize the cross entropy with the observed word distribution. Finally, we propose the adaptive EM (AEM) algorithm that converges faster and more accurate than the current state-of-the-art SparseLDA [20] and AliasLDA [12] from small to big data and LDA models. The core idea is that the number of active topics, measured by the residuals between E-steps at successive iterations, decreases significantly, leading to the amortized σ(1) time complexity in terms of the number of topics. The open source code of AEM is available at GitHub.

It is still challenging in telecommunication (telco) industry to accurately locate mobile devices (MDs) at city-scale using the measurement report (MR) data, which measure parameters of radio signal strengths when MDs connect with base stations (BSs) in telco networks for making/receiving calls or mobile broadband (MBB) services. In this paper, we find that the widely-used location based services (LBSs) have accumulated lots of over-the-top (OTT) global positioning system (GPS) data in telco networks, which can be automatically used as training labels for learning accurate MR-based positioning systems. Benefiting from these telco big data, we deploy a context-aware coarse-to-fine regression (CCR) model in Spark/Hadoop-based telco big data platform for city-scale localization of MDs with two novel contributions. First, we design map-matching and interpolation algorithms to encode contextual information of road networks. Second, we build a two-layer regression model to capture coarse-to-fine contextual features in a short time window for improved localization performance. In our experiments, we collect 108 GPS-associated MR records in the centroid of Shanghai city with 12 x 11 square kilometers for 30 days, and measure four important properties of real-world MR data related to localization errors: stability, sensitivity, uncertainty and missing values. The proposed CCR works well under different properties of MR data and achieves a mean error of 110m and a median error of $80m$, outperforming the state-of-art range-based and fingerprinting localization methods.

We study safe zones for service subscriptions in a volunteered geographic service setting, covering the concepts, properties, and algorithms needed for the use of weighted imprecise Voronoi cells as safe zones. Empirical performance studies on both synthetic and real datasets offer insights into the efficiency and scalability of our proposal. For a comprehensive coverage, see the full version of the paper.

Owing to the proliferation of mobile devices and their corresponding app ecosystems, more and more people are accessing the internet via various mobile apps, which generates tremendous volume of mobile data. Despite the growing importance of these mobile apps, we have a rather sparse understanding of how they are accessed and what issues affect their usage patterns. To address this problem, we perform a comprehensive measurement on large-scale anonymized network data collected from a tier-1 cellular carrier in China. In this measurement, we characterize the usage pattern of mobile apps and exhibit how the mobility, geospatial properties and behaviours of subscribers affect their mobile app usage at a fine-grained level.

Telecommunication (telco) operators aim to provide users with optimized services and bandwidth in a timely manner. The goal is to increase user experience while retaining profit. To do this, knowing the changing behavior patterns of users through their activity levels in advance can be a great help for operators to adjust their management strategies and reduce operational risk. To achieve this goal, the operators can make use of knowledge discovered from telco’s historical mobile broadband (MBB) records to predict mobile access activity level at an early stage. In this article, we report our research in a real-world telco setting involving more than one million telco users. Our novel contribution includes representing users as documents containing a collection of changing spatiotemporal “words” that express user behavior. By extracting users’ space-time access records in MBB data, we use latent Dirichlet allocation (LDA) to learn user-specific compact topic features for user activity level prediction. We propose a scalable online expectation-maximization (OEM) algorithm that can scale LDA to massive MBB data, which is significantly faster than several state-of-the-art online LDA algorithms. Using these real-world MBB data, we confirm high performance in user activity level prediction. In addition, we show that the inferred topics indicate that future activity level anomalies correlate highly with early skewed bandwidth supply and demand relations. Thus, our prediction system can also guide the telco operators to balance the telecommunication network in terms of supply-demand relations, saving deployment costs and energy of cell towers in the future.

We provide techniques that enable a scalable so-called Volunteered Geographic Services system. This system targets the increasing populations of online mobile users, e.g., smartphone users, enabling such users to provide location-based services to each other, thus enabling citizen reporter or citizen as a sensor scenarios. More specifically, the system allows users to register as service volunteers, or micro-service providers, by accepting service descriptions and periodically updated locations from such volunteers; and the system allows users to subscribe to notifications of available, nearby relevant services by accepting subscriptions, formalized as continuous queries, that take service preferences and user locations as arguments and return relevant services. Services are ranked according to their relevance and distance to a query, and the highest ranked services are returned. The key challenge addressed is that of scalably providing up-to-date results to queries when the query locations change continuously. This is achieved by the proposal of a new so-called safe-zone model. With safe zones, query results are accompanied by safe zones with the property that a query result remains the same for all locations in its safe zone. Then, query users need only notify the system when they exit their current safe zone. Existing safe-zone models fall short in the papers setting. The new model is enabled by (i) weighted and (ii) set weighted imprecise Voronoi cells. The paper covers underlying concepts, properties, and algorithms, and it covers applications in VGS tracking and presents findings of empirical performance studies.

Understanding co-occurrence in urban human mobility (i.e. people from two regions visit an urban place during the same time span) is of great value in a variety of applications, such as urban planning, business intelligence, social behavior analysis, as well as containing contagious diseases. In recent years, the widespread use of mobile phones brings an unprecedented opportunity to capture large-scale and fine-grained data to study co-occurrence in human mobility. However, due to the lack of systematic and efficient methods, it is challenging for analysts to carry out in-depth analyses and extract valuable information. In this paper, we present TelCoVis, an interactive visual analytics system, which helps analysts leverage their domain knowledge to gain insight into the co-occurrence in urban human mobility based on telco data. Our system integrates visualization techniques with new designs and combines them in a novel way to enhance analysts' perception for a comprehensive exploration. In addition, we propose to study the correlations in co-occurrence (i.e. people from multiple regions visit different places during the same time span) by means of biclustering techniques that allow analysts to better explore coordinated relationships among different regions and identify interesting patterns. The case studies based on a real-world dataset and interviews with domain experts have demonstrated the effectiveness of our system in gaining insights into co-occurrence and facilitating various analytical tasks.

It is well known that the key issue of online marketing is to accurately find the target user groups for the corresponding advertisements. Traditionally, the advertising products target user groups based on search keywords (e.g. AdWords), page visiting (e.g. AdSense), and etc. In this work, we explore a new targeting strategy - targeting users based on their downloaded apps. Specifically, we make use of a subset of the data from the Huawei App Store, consisting of 20,169,033 users and 122,875 apps with 453,346,250 downloads during one year. For each marketing job, the advertiser only need to label a small set of apps, usually around 10 apps, that the target users might be interested in. Our system xRank will automatically find a list of top potential target users for the advertiser. We implement xRank with very efficient performance on the top of Hadoop to be capable for a real web-scale dataset, and then conducted our system to several real marketing tasks. The results show that, for each marketing task, with only a few labels, xRank can effectively find a precise target group of users, and can also significantly improved the effectiveness of our online marketing compared to the rule-based approaches in the current system.

The increasing prevalence of sensors and mobile devices has led to an explosive increase of the scale of spatio-temporal data in the form of trajectories. A trajectory aggregate query, as a fundamental functionality for measuring trajectory data, aims to retrieve the statistics of trajectories passing a user-specified spatio-temporal region. A large-scale spatio-temporal database with big disk-resident data takes very long time to produce exact answers to such queries. Hence, approximate query processing with a guaranteed error bound is a promising solution in many scenarios with stringent response-time requirements. In this paper, we study the problem of approximate query processing for trajectory aggregate queries. We show that it boils down to the distinct value estimation problem, which has been proven to be very hard with powerful negative results given that no index is built. By utilizing the well-established spatio-temporal index and introducing an inverted index to trajectory data, we are able to design random index sampling (RIS) algorithm to estimate the answers with a guaranteed error bound. To further improve system scalability, we extend RIS algorithm to concurrent random index sampling (CRIS) algorithm to process a number of trajectory aggregate queries arriving concurrently with overlapping spatio-temporal query regions. To demonstrate the efficacy and efficiency of our sampling and estimation methods, we applied them in a real large-scale user trajectory database collected from a cellular service provider in China. Our extensive evaluation results indicate that both RIS and CRIS outperform exhaustive search for single and concurrent trajectory aggregate queries by two orders of magnitude in terms of the query processing time, while preserving a relative error ratio lower than 10\%, with only 1% search cost of the exhaustive search method.

The impact of inclement weather to urban traffic has been widely observed and studied for many years, with focus primarily on individual road segments by analyzing data from roadside deployed monitors. However, two fundamental questions are still open: (i) how to identify regional weather-traffic sensitivity index throughout a city, that indicates the degree to which the region traffic in a city is impacted by weather changes, (ii) among complex regional features, such as road structure and population density, how to dissect the most influential regional features that drive the urban region traffic to be more vulnerable to weather changes. Answering these questions is unprecedentedly important for urban planners to understand the functional characteristics of various urban regions throughout a city, and to improve traffic prediction and learn the key factors in urban planning. However, these two questions are nontrivial to answer, because urban traffic changes dynamically over time and is essentially affected by many other factors, which may dominate the overall impact. In this work, we make the first study on these questions, by developing a weather-traffic index (WTI) system. The system includes two main components: WTI establishment and key factor analysis. Using the proposed system, we conducted comprehensive empirical study in Shanghai, and the WTI extracted have been validated to be surprisingly consistent with real world observations. Further regional key factor analysis yields interesting results. For example, house age has significant impact on WTI, which sheds light on future urban planning and reconstruction.

We show that telco big data can make churn prediction much more easier from the $3$V's perspectives: Volume, Variety, Velocity. Experimental results confirm that the prediction performance has been significantly improved by using a large volume of training data, a large variety of features from both business support systems (BSS) and operations support systems (OSS), and a high velocity of processing new coming data. We have deployed this churn prediction system in one of the biggest mobile operators in China. From millions of active customers, this system can provide a list of prepaid customers who are most likely to churn in the next month, having $0.96$ precision for the top $50000$ predicted churners in the list. Automatic matching retention campaigns with the targeted potential churners significantly boost their recharge rates, leading to a big business value.

Differential privacy (DP) has been widely explored in academia recently but less so in industry possibly due to its strong privacy guarantee. This paper makes the first attempt to implement three basic DP architectures in the deployed telecommunication (telco) big data platform for data mining applications. We find that all DP architectures have less than 5% loss of prediction accuracy when the weak privacy guarantee is adopted (e.g., privacy budget parameter ε ≥ 3). However, when the strong privacy guarantee is assumed (e.g., privacy budget parameter ε ≤ 0:1), all DP architectures lead to 15% ~ 30% accuracy loss, which implies that real-word industrial data mining systems cannot work well under such a strong privacy guarantee recommended by previous research works. Among the three basic DP architectures, the Hybridized DM (Data Mining) and DB (Database) architecture performs the best because of its complicated privacy protection design for the specific data mining algorithm. Through extensive experiments on big data, we also observe that the accuracy loss increases by increasing the variety of features, but decreases by increasing the volume of training data. Therefore, to make DP practically usable in large-scale industrial systems, our observations suggest that we may explore three possible research directions in future: (1) Relaxing the privacy guarantee (e.g., increasing privacy budget ε) and studying its effectiveness on specific industrial applications; (2) Designing specific privacy scheme for specific data mining algorithms; and (3) Using large volume of data but with low variety for training the classification models.

The emerging geo-social networks bring us attractive location-based services as well as serious location-related privacy threats. Location information of users in geo-social networks might be revealed by friends carelessly, or deduced by users curiously or even maliciously. In order to avoid location leakages, we propose collaborative privacy management in geo-social networks. Users specify and broadcast their preferences on location-related privacies in advance, so that potential leakages can be reported automatically when new resources arrive. If necessary, the associated spatial and/or temporal information of resources will be tweaked according to the privacy preferences of involving users, so that "old" leakages can be eliminated while ensuring that "new" ones are not introduced. We design algorithms for such tweaks and construct experiments on a simulated dataset to demonstrate their usability and applicability.

Exploring massive mobile data for location-based services (LBS) becomes one of the key challenges in mobile data mining. In this paper, we propose a framework that uses large-scale cell tower data dumps and extracts points-of-interest (POIs) from a social network web site called Weibo, and provides new LBS based on these two data sets, i.e., predicting the existence of POIs and the number of POIs in a certain area. We use Voronoi diagram to divide a city area into non-overlapping regions, and a k-means clustering algorithm to aggregate neighboring cell towers into region groups. A supervised learning algorithm is adopted to build up a model between the number of connections of cell towers and the POIs in different region groups, where a classification or regression model is used to predict the POI existence or the number of POIs, respectively. We studied 12 state-of-the-art classification and regression algorithms, and the experimental results demonstrate the feasibility and effectiveness of the proposed framework.

We demonstrate OceanRT, a novel cloud-based infrastructure that performs online analytics in real time, over large-scale temporal data such as call logs from a telecommunication company. Apart from proprietary systems for which few details have been revealed, most existing big-data analytics systems are built on top of an offline, MapReduce-style infrastructure, which inherently limits their efficiency. In contrast, OceanRT employs a novel computing architecture consisting of interconnected Access Query Engines (AQEs), as well as a new storage scheme that ensures data locality and fast access for temporal data. Our preliminary evaluation shows that OceanRT can be up to 10x faster than Impala [10], 12x faster than Shark [5], and 200x faster than Hive [13]. The demo will show how OceanRT manages a real call log dataset (around 5TB per day) from a large mobile network operator in China. Besides presenting the processing of a few preset queries, we also allow the audience to issue ad hoc HiveQL [13] queries, watch how OceanRT answers them, and compare the speed of OceanRT with its competitors.

With the increasing prevalence of versatile mobile devices and the fast deployment of broadband mobile networks, a huge volume of Mobile Broadband (MBB) data has been generated over time. The MBB data naturally contain rich information of a large number of mobile users, covering a considerable fraction of whole population nowadays, including the mobile applications they are using at different locations and time; the MBB data may present the unprecedentedly large knowledge base of human behavior which has highly recognized commercial and social value. However, the storage, management and analysis of the huge and fast growing volume of MBB data post new and significant challenges to the industrial practitioners and research community. In this demonstration, we present a new, MBB data tailored, distributed analytic system named OceanST which has addressed a series of problems and weaknesses of the existing systems, originally designed for more general purpose and capable to handle MBB data to some extent. OceanST is featured by ( i ) efficiently loading of ever-growing MBB data, ( ii ) a bunch of spatiotemporal aggregate queries and basic analysis APIs frequently found in various MBB data application scenarios, and ( iii ) sampling-based approximate solution with provable accuracy bound to cope with huge volume of MBB data. The demonstration will show the advantage of OceanST in a cluster of 5 machines using 3TB data.

Privacy is one of the major concerns when publishing or sharing social network data for social science research and business analysis. Recently, researchers have developed privacy models similar to k-anonymity to prevent node reidentification through structure information. However, even when these privacy models are enforced, an attacker may still be able to infer one's private information if a group of nodes largely share the same sensitive labels (i.e., attributes). In other words, the label-node relationship is not well protected by pure structure anonymization methods. Furthermore, existing approaches, which rely on edge editing or node clustering, may significantly alter key graph properties. In this paper, we define a k-degree-l-diversity anonymity model that considers the protection of structural information as well as sensitive labels of individuals. We further propose a novel anonymization methodology based on adding noise nodes. We develop a new algorithm by adding noise nodes into the original graph with the consideration of introducing the least distortion to graph properties. Most importantly, we provide a rigorous analysis of the theoretical bounds on the number of noise nodes added and their impacts on an important graph property. We conduct extensive experiments to evaluate the effectiveness of the proposed technique.

The privacy protection of graph data has become more and more important in recent years. Many works have been proposed to publish a privacy preserving graph. All these works prefer publishing a graph, which guarantees the protection of certain privacy with the smallest change to the original graph. However, there is no guarantee on how the utilities are preserved in the published graph. In this paper, we propose a general fine-grained adjusting framework to publish a privacy protected and utility preserved graph. With this framework, the data publisher can get a trade-off between the privacy and utility according to his customized preferences. We used the protection of a weighted graph as an example to demonstrate the implementation of this framework.

Dataspaces consist of large-scale heterogeneous data. The query interface of accessing tuples should be provided as a fundamental facility by practical dataspace systems. Previously, an efficient index has been proposed for queries with keyword neighborhood over dataspaces. In this paper, we study the materialization and decomposition of dataspaces, in order to improve the query efficiency. First, we study the views of items, which are materialized in order to be reused by queries. When a set of views are materialized, it leads to select some of them as the optimal plan with the minimum query cost. Efficient algorithms are developed for query planning and view generation. Second, we study the partitions of tuples for answering top-k queries. Given a query, we can evaluate the score bounds of the tuples in partitions and prune those partitions with bounds lower than the scores of top-k answers. We also provide theoretical analysis of query cost and prove that the query efficiency cannot be improved by increasing the number of partitions. Finally, we conduct an extensive experimental evaluation to illustrate the superior performance of proposed techniques.

Due to the popularity of social networks, many proposals have been proposed to protect the privacy of the networks. All these works assume that the attacks use the same background knowledge. However, in practice, different users have different privacy protect requirements. Thus, assuming the attacks with the same background knowledge does not meet the personalized privacy requirements, meanwhile, it looses the chance to achieve better utility by taking advantage of differences of users' privacy requirements. In this paper, we introduce a framework which provides privacy preserving services based on the user's personal privacy requests. Specifically, we define three levels of protection requirements based on the gradually increasing attacker's background knowledge and combine the label generalization protection and the structure protection techniques (i.e. adding noise edge or nodes) together to satisfy different users' protection requirements. We verify the effectiveness of the framework through extensive experiments.

FPGAs are widely used in today's embedded systems design due to their low cost, high performance, and reconfigurability. Partially RunTime-Reconfigurable (PRTR) FPGAs, such as Virtex-2 Pro and Virtex-4 from Xilinx, allow part of the FPGA area to be reconfigured while the remainder continues to operate without interruption, so that HW tasks can be placed and removed dynamically at runtime. We address two problems related to HW task scheduling on PRTR FPGAs: (1) HW/SW partitioning. Given an application in the form of a task graph with known execution times on the HW (FPGA) and SW (CPU), and known area sizes on the FPGA, find an valid allocation of tasks to either HW or SW and a static schedule with the optimization objective of minimizing the total schedule length (makespan). (2) Pipelined scheduling. Given an input task graph, construct a pipelined schedule on a PRTR FPGA with the goal of maximizing system throughput while meeting a given end-to-end deadline. Both problems are NP-hard. Satisfiability Modulo Theories (SMT) is an extension to SAT by adding the ability to handle arithmetic and other decidable theories. We use the SMT solver Yices with Linear Integer Arithmetic (LIA) theory as the optimization engine for solving the two scheduling problems. In addition, we present an efficient heuristic algorithm based on kernel recognition for the pipelined scheduling problem, a technique borrowed from SW pipelining, to overcome the scalability problem of the SMT-based optimal solution technique.

FPGAs are often used together with a CPU as hardware accelerators. A runtime reconfigurable FPGA allows part of the FPGA area to be reconfigured while the remainder continues to operate without interruption, so that hardware tasks can be placed and removed dynamically at runtime. In this paper, we formulate and solve the problem of optimal hardware/software partitioning and static task scheduling for a hybrid FPGA/CPU device, with the optimization objective of minimizing the total schedule length, in the framework of satisfiability modulo theories (SMT) with linear integer arithmetic.

As Moore's law comes to an end, multiprocessor systems are becoming ubiquitous in today's embedded systems design. In this paper, we address the problem of mapping a homogeneous synchronous dataflow (HSDF) graph onto a multiprocessor platform with the objective of maximizing system throughput. We present two optimization approaches based on branch-and-bound and SAT-solving to explore the design space of all possible actor-to-processor mappings and static order schedules on each processor. In the logic-based benders decomposition (LBBD) approach, we decompose the problem into a master problem of finding a feasible actor mapping and scheduling, and a sub-problem of deadlock-checking and throughput computation. In the integrated approach, we integrate branch-and-bound search into the SAT engine to achieve more effective search tree pruning and better scalability. Performance evaluation shows that the integrated approach outperforms the LBBD approach by a large margin.

Time-triggered protocol (TTP) is a time-division multiple access (TDMA)-based bus protocol designed for use in safety-critical avionics and automotive distributed embedded systems. Design space exploration (DSE) for TTP-based distributed embedded system involves searching through a vast design space of possible task-to-CPU mappings, task/message schedules and bus access configurations to achieve certain design objectives. In this paper, we present an efficient two-level hierarchical DSE framework for TTP-based distributed embedded systems, with the objective of minimizing the total bus utilization while meeting an end-to-end deadline constraint. Logic-based Benders decomposition (LBBD) is used to divide the problem into a master problem of mapping tasks to CPU nodes to minimize the total bus utilization, solved with a satisfiability modulo theories (SMT) solver, and a subproblem of finding a feasible solution of bus access configuration and task/message schedule under an end-to-end deadline constraint for a given task-to-CPU mapping, solved with a constraint programming (CP) solver. Performance evaluation results show that our approach is scalable to problems with realistic size.

Time-Triggered Protocol for the bus and static task scheduling for the CPU are widely used in safety-critical distributed embedded systems. Researchers have presented efficient heuristic algorithms to jointly optimize static task and bus access schedules. In this paper, we use the model checker SPIN to provide a flexible and configurable technique for obtaining provably optimal solutions, and evaluate its performance tradeoffs compared to heuristic algorithms.

Real-time scheduling for FPGAs presents unique challenges to traditional real-time scheduling theory, since it is similar to, but more general than multi-processor scheduling. In his paper, we address two problems of static task scheduling on a partially runtime reconfigurable FPGA: finding an optimal static schedule for a task graph with the optimization objective of minimizing the total schedule length, and finding a feasible static schedule for a set of periodic tasks within a hyper-period with the objective of meeting all deadlines. We model the multi-tasking system with timed automata and use reachability analysis of the UPPAAL model-checker to explore the design space and find an optimal or feasible schedule

In this paper, we address the problem of static scheduling and software synthesis for dataflow graphs with the symbolic model-checker NuSMV using a two-step process: first use model-checking to obtain a static schedule with the objective of minimizing the data buffer size, then synthesize efficient code from the static schedule with the objective of minimizing code size and performance overheads due to runtime dynamic decisions. We show the effectiveness of these techniques using a number of digital signal processing examples.

Context-aware applications can better meet users' needs when sensing agents installed in the environment automatically provide input relevant to the application. However, this non-intrusive context usage may cause privacy concerns since sensitive user data could be leaked to unauthorized parties. Therefore, data privacy protection becomes one of the major issues for context-aware applications. In this paper, in order to provide services based on various levels of privacy concerns, we extend the Platform for Privacy Preferences of W3C and define a specification for representing user privacy preferences for context-aware applications. We also propose a privacy infrastructure, which could be installed as a plug-in service for middleware supporting context-aware applications. This infrastructure enables the middleware to automatically generate a privacy policy and the user preference file according to the current context. The middleware simply matches these two files to decide whether to proceed with the application. We demonstrate the efficacy of this approach through a prototype implementation.