Marketing campaigns are a set of strategic activities that can promote a business's goal. The effect prediction for marketing campaigns in a real industrial scenario is very complex and challenging due to the fact that prior knowledge is often learned from observation data, without any intervention for the marketing campaign. Furthermore, each subject is always under the interference of several marketing campaigns simultaneously. Therefore, we cannot easily parse and evaluate the effect of a single marketing campaign. To the best of our knowledge, there are currently no effective methodologies to solve such a problem, i.e., modeling an individual-level prediction task based on a hierarchical structure with multiple intertwined events. In this paper, we provide an in-depth analysis of the underlying parse tree-like structure involved in the effect prediction task and we further establish a Hierarchical Capsule Prediction Network (HapNet) for predicting the effects of marketing campaigns. Extensive results based on both the synthetic data and real data demonstrate the superiority of our model over the state-of-the-art methods and show remarkable practicability in real industrial applications.

Due to their high retrieval efficiency and low storage cost, cross-modal hashing methods have attracted considerable attention. Generally, compared with shallow cross-modal hashing methods, deep cross-modal hashing methods can achieve a more satisfactory performance by integrating feature learning and hash codes optimizing into a same framework. However, most existing deep cross-modal hashing methods either cannot learn a unified hash code for the two correlated data-points of different modalities in a database instance or cannot guide the learning of unified hash codes by the feedback of hashing function learning procedure, to enhance the retrieval accuracy. To address the issues above, in this paper, we propose a novel end-to-end Deep Cross-Modal Hashing with Hashing Functions and Unified Hash Codes Jointly Learning (DCHUC). Specifically, by an iterative optimization algorithm, DCHUC jointly learns unified hash codes for image-text pairs in a database and a pair of hash functions for unseen query image-text pairs. With the iterative optimization algorithm, the learned unified hash codes can be used to guide the hashing function learning procedure; Meanwhile, the learned hashing functions can feedback to guide the unified hash codes optimizing procedure. Extensive experiments on three public datasets demonstrate that the proposed method outperforms the state-of-the-art cross-modal hashing methods.

Multi-task learning(MTL) is an open and challenging problem in various real-world applications. The typical way of conducting multi-task learning is establishing some global parameter sharing mechanism across all tasks or assigning each task an individual set of parameters with cross-connections between tasks. However, for most existing approaches, all tasks just thoroughly or proportionally share all the features without distinguishing the helpfulness of them. By that, some tasks would be intervened by the unhelpful features that are useful for other tasks, leading to undesired negative transfer between tasks. In this paper, we design a novel architecture named the Multiple-level Sparse Sharing Model (MSSM), which can learn features selectively and share knowledge across all tasks efficiently. MSSM first employs a field-level sparse connection module (FSCM) to enable much more expressive combinations of feature fields to be learned for generalization across tasks while still allowing for task-specific features to be customized for each task. Furthermore, a cell-level sparse sharing module (CSSM) can recognize the sharing pattern through a set of coding variables that selectively choose which cells to route for a given task. Extensive experimental results on several real-world datasets show that MSSM outperforms SOTA models significantly in terms of AUC and LogLoss metrics.

Multi-dimensional Hawkes processes (MHP) has been widely used for modeling temporal events. However, when MHP was used for modeling events with spatio-temporal characteristics, the spatial information was often ignored despite its importance. In this paper, we introduce a framework to exploit MHP for modeling spatio-temporal events by considering both temporal and spatial information. Specifically, we design a graph regularization method to effectively integrate the prior spatial structure into MHP for learning influence matrix between different locations. Indeed, the prior spatial structure can be first represented as a connection graph. Then, a multi-view method is utilized for the alignment of the prior connection graph and influence matrix while preserving the sparsity and low-rank properties of the kernel matrix. Moreover, we develop an optimization scheme using an alternating direction method of multipliers to solve the resulting optimization problem. Finally, the experimental results show that we are able to learn the interaction patterns between different geographical areas more effectively with prior connection graph introduced for regularization.

Improving safety and convenience is always the top priority in designing today's intelligent transportation system. In this paper, we study the problem of how to manage vehicle traffic at intersections by jointly considering safety, driver's comfort, and efficiency, in vehicular ad hoc networks. We propose a distributed intersection management protocol (DIMP), which distributedly coordinates vehicle traffic from different directions by making vehicles exchange critical driving information and adaptively react based on the information. DIMP dynamically guides vehicles to adjust their speed in a way such that both safety and driver's comfort are satisfied. By following DIMP, vehicles can pass the intersections safely and efficiently at a comfortable speed during acceleration/deceleration. We extensively evaluate DIMP, and the evaluation results show that DIMP is both effective and efficient in managing vehicle traffic at intersections.

Accurately identifying time-invariant operational relationships among different components is critical to autonomic management of complex manufactural systems. In this paper, we collect time series of sensor readings from manufacturing systems, and propose a solution leveraging Sparse Group LASSO to discover structured pairwise nonlinear relationships and quantify them by mathematical formulas. We consider both real-life operational patterns and underlying physical reactions inside the manufactural systems, which leads to a learning formulation for combined periodic and aperiodic system behaviors. An accelerated gradient descent algorithm is developed to efficiently solve the related optimization problem. We estimate sample correlations between proximal time points to improve the accuracy of the discovered relationships and the nonlinear quantitative formulas. The method is evaluated using both synthetic and real-world datasets, which shows superior performance over the state of the art in discovering nonlinear relationships in manufactural systems.

Complex systems are prevalent in many fields such as finance, security and industry. A fundamental problem in system management is to perform diagnosis in case of system failure such that the causal anomalies, i.e., root causes, can be identified for system debugging and repair. Recently, invariant network has proven a powerful tool in characterizing complex system behaviors. In an invariant network, a node represents a system component, and an edge indicates a stable interaction between two components. Recent approaches have shown that by modeling fault propagation in the invariant network, causal anomalies can be effectively discovered. Despite their success, the existing methods have a major limitation: they typically assume there is only a single and global fault propagation in the entire network. However, in real-world large-scale complex systems, it's more common for multiple fault propagations to grow simultaneously and locally within different node clusters and jointly define the system failure status. Inspired by this key observation, we propose a two-phase framework to identify and rank causal anomalies. In the first phase, a probabilistic clustering is performed to uncover impaired node clusters in the invariant network. Then, in the second phase, a low-rank network diffusion model is designed to backtrack causal anomalies in different impaired clusters. Extensive experimental results on real-life datasets demonstrate the effectiveness of our method.

An accurate and automated identification of operational behavior switching is critical to the autonomic management of complex systems. In this paper, we collect sensor readings from those systems, which are treated as time series, and propose a solution to discover switching behaviors by inferring the relationship changes among massive time series. The method first learns a sequence of local relationship models that can best fit the time series data, and then combines the changes of local relationships to identify the system level behavior switching. In the local relationship modeling, we formulate the underlying switching identification as a segmentation problem, and propose a sophisticated optimization algorithm to accurately discover different segments in time series. In addition, we develop a hierarchical optimization strategy to further improve the efficiency of segmentation. To unveil the system level behavior switching, we present a density estimation and mode search algorithm to effectively aggregate the segmented local relationships so that the global switch points can be captured. Our method has been evaluated on both synthetic data and datasets from real systems. Experimental results demonstrate that it can successfully discover behavior switching in different systems.

The long term operation of physical systems inevitably leads to their wearing out, and may cause degradations in performance or the unexpected failure of the entire system. To reduce the possibility of such unanticipated failures, the system must be monitored for tell-tale symptoms of degradation that are suggestive of imminent failure. In this work, we introduce a novel time series analysis technique that allows the decomposition of the time series into trend and fluctuation components, providing the monitoring software with actionable information about the changes of the system's behavior over time. We analyze the underlying problem and formulate it to a Quadratic Programming (QP) problem that can be solved with existing QP-solvers. However, when the profiling resolution is high, as generally required by real-world applications, such a decomposition becomes intractable to general QP-solvers. To speed up the problem solving, we further transform the problem and present a novel QP formulation, Non-negative QP, for the problem and demonstrate a tractable solution that bypasses the use of slow general QP-solvers. We demonstrate our ideas on both synthetic and real datasets, showing that our method allows us to accurately extract the degradation phenomenon of time series. We further demonstrate the generality of our ideas by applying them beyond classic machine prognostics to problems in identifying the influence of news events on currency exchange rates and stock prices. We fully implement our profiling system and deploy it into several physical systems, such as chemical plants and nuclear power plants, and it greatly helps detect the degradation phenomenon, and diagnose the corresponding components.

The rapid growth of mobile app traffic brings huge pressure to today's cellular networks. While this fact is commonly concerned by all the mobile carriers, little work has been done to analyze app's network resource usage. In this paper, we, for the first time, profile network resource usages for mobile apps by establishing a quantitative mapping between them. We design AppWiR, a crowdsourcing-based mining system that collects app behavior information from phones and mines hundreds of indicators in different network layers. It builds a two-layer causal relationship among app behaviors, network traffics, and network resources. With such relationship knowledge, we model, quantify, and predict the network resource usage for each mobile app. We fully implement the AppWiR crowdsourcing app in Android smartphones to collect data from users. To evaluate its real-world performance, we deploy the AppWiR system and conduct a trial in a leading LTE carrier's network in different geographic areas and network coverages. The trial shows that the AppWiR can accurately estimate and predict the resource usages for mobile apps.

Scalable and diagnosable are the two most crucial needs for voice call quality assessment in mobile networks. However, while these two requirements are widely accepted by mobile carriers, they do not receive enough attention during the development. Current related research mainly focuses on audio feature analysis, which is costly, sensitive to language and tones, and infeasible to be applied to large-scale mobile networks. In this paper, we revisit this problem, and for the first time explore wireless network, the causal factor that directly impacts the mobile voice quality but yet lacks attention for decades. We design CrowdMi, a wireless analytical tool that model the mobile voice quality by crowdsourcing and mining the network indicators of cellphones. CrowdMi mines hundreds of network indicators to build a causal relationship between voice quality and network conditions, and carefully calibrates the model according to the widely accepted perceptual objective listening quality assessment (POLQA) voice assessment standard. We implement a light-load CrowdMi Client App in Android smartphones, which automatically collects data through user crowdsourcing and outputs to the CrowdMi Server in our data center that runs the mining algorithm. We conduct a pilot trial in VoLTE network in different geographical areas and network coverages. The trial shows that the CrowdMi does not require any additional hardware or human effort, and has very high model accuracy and strong diagnosability.

Sensor nodes deployed outdoors are subject to environmental detriments and often need to cache data for an extended period of time. This paper introduces sensor nodes which are robust to environmental damages, and proposes to utilize Network Coding to back up data in the robust sensors for future data retrieval in an energy efficient way. Our goal is to help regular sensors select robust sensors to back up their data with low energy consumption, such that when needed, all the data can be retrieved by querying only a subset of robust sensors. We formally formulate this backup problem, theoretically prove its NP-Completeness, discover two novel theoretical guidelines for problem solving, and propose two algorithms accordingly to tackle this NP-C problem. The guidelines are based on random linear network coding and provide lower bounds of the number of robust sensors that each regular sensor should choose for data backup, such that the required fault tolerance is provided. A centralized algorithm and a distributed algorithm are developed based on the guidelines such that regular sensors can back up their data efficiently. Both analysis and simulation show our algorithms are effective in achieving fault tolerance, low energy consumption, and high retrieval efficiency.

Sensor nodes deployed outdoors for field surveillance are subject to environmental detriments. In this article, we propose a heterogeneous sensor network composed of sensor nodes with different environmental survivability to make it robust to environmental damage and keep it at a reasonable cost. We, for the first time, study the scheduling problem in such heterogeneous sensor networks for critical location surveillance applications. Our goal is to monitor all the critical points for as long as possible under different environmental conditions. We identify the underlying problem, theoretically prove its NP-complete nature, and propose a novel adaptive greedy scheduling algorithm to solve the problem. The algorithm incorporates several heuristics to schedule the activity of both regular and robust sensors to monitor all the critical points, while at the same time minimizing and balancing the network energy consumption. Simulation results show that our algorithm efficiently solves the problem and outperforms other alternatives.

GPS navigators have been widely adopted by drivers. However, due to the sensibility of GPS signals to terrain, vehicles cannot get their locations when they are inside a tunnel or on a road surrounded by high-rises where satellite signal is blocked. This incurs safety and convenience problems. To address the issue, we propose a novel Grid-based On-road localizaTion system (GOT), where vehicles with and without accurate GPS signals self-organize into a Vehicular Ad Hoc Network (VANET), exchange location and distance information and help each other to calculate an accurate position for all the vehicles inside the network. The location information can be exchanged among vehicles one or multiple hops away in this paper. We explore fuzzy geometric relationship among vehicles, and apply a novel grid-based mechanism to evaluate the geometric relationships and calculate vehicle locations. Simulation shows our GOT system is effective and efficient in calculating vehicular positions.

Aerial image simulation is a fundamental problem in advanced lithography for chip fabrication. Since it requires a huge number of mathematical computations, an efficient yet accurate implementation becomes a necessity. In the literature, GPU or FPGA has demonstrated its potential for accelerating aerial image simulation. However, the comparisons of GPU or FPGA to CPU were not done thoroughly. In particular, careful tunings for the CPU-based method were missing in the previous works, while the recent CPU architectures have significant modifications toward high performance computing capabilities. In this paper, we present and discuss several algorithms for the aerial image simulation on multi-core SIMD CPU. Our fastest method achieves up to 73X speedup over the baseline serial approach and outperforms the state-of-the-art GPU-based approach by up to 2X speedup on a single hex-core SIMD CPU. We show that the performance on the multi-core SIMD CPU is promising, and that careful CPU tunings are necessary in order to exploit its computing capabilities.

Conventional CMOS devices are facing an increasing number of challenges as their feature sizes scale down. Graphene nanoribbon (GNR) based devices are shown to be a promising replacement of traditional CMOS at future technology nodes. However, all previous works on GNRs focus at the device level. In order to integrate these devices into electronic systems, routing becomes a key issue. In this article, the GNR routing problem is studied for the first time. We formulate the GNR routing problem as a minimum hybrid-cost shortest path problem on triangular mesh (“hybrid” means that we need to consider both the length and the bending of the routing path). We show that by graph expansion, this minimum hybrid-cost shortest path problem can be solved by applying the conventional shortest path algorithm on the expanded graph. Experimental results show that our GNR routing algorithm effectively handles the hybrid cost.

Efficient data dissemination to a fixed number of receivers in VANET is a new issue and is challenging considering the dynamic nature of VANET. We aim to accurately control the number of receivers, achieve low dissemination delay and incur only small communication overhead. To achieve the goal, we design DOVE (Data Dissemination to A Fixed Number of Receivers in VANET) inspired by processor scheduling, which treats roads as processors to optimize the workload assignment and improves the efficiency of on-road dissemination. DOVE reaches the desired number of receivers with little inaccuracy and minimizes the dissemination delay with low communication overhead. We enhance our protocol with workload backup to deal with vehicles' quitting the network. We utilize the unique characteristics of VANET and propose heuristics accordingly to significantly reduce the dissemination delay and overhead. Simulation results show that our scheme disseminates data to all the pre-given number of receivers in a very light overhead and low delay.

Escape routing for packages and printed circuit boards (PCBs) has been studied extensively in the past. Network flow is pervasively used to model this problem. However, none of the previous works correctly models the diagonal capacity, which is essential for 45° routing in most packages and PCBs. As a result, existing algorithms may either produce routing solutions that violate the diagonal capacity or fail to output a legal routing even though there exists one. In this paper, we propose a new network flow model that guarantees the correctness when diagonal capacity is taken into consideration. This model leads to the first optimal algorithm for escape routing. We also extend our model to handle missing pins.

Conventional CMOS devices are facing an increasing number of challenges as their feature sizes scale down. Graphene nanoribbon (GNR) based devices are shown to be a promising replacement of traditional CMOS at future technology nodes. However, all previous works on GNRs focus at the device level. In order to integrate these devices into electronic systems, routing becomes a key issue. In this paper, the GNR routing problem is studied for the first time. We formulate the GNR routing problem as a minimum hybrid-cost shortest path problem on triangular mesh (“hybrid” means that we need to consider both the length and the bending of the routing path). In order to model this hybrid-cost problem, we apply graph expansion and introduce a shortest red-black path problem on the expanded graph. We then propose an algorithm that solves the shortest red-black path problem optimally. This algorithm is then used in a negotiated congestion based routing scheme. Experimental results show that our GNR routing algorithm effectively handles the hybrid cost.

Aerial image simulation is a fundamental problem for modern VLSI design. It requires a huge amount of numerical computation. The recent advancement of general purpose GPU computing provides an excellent opportunity to parallelize the aerial image simulation and achieve great speedup. In this paper, we present and discuss two GPU-based aerial image simulation algorithms. We show through experiments that the fastest algorithm we propose can achieve 50X to 60X speedup over the CPU based serial algorithm. The error of our approach is shown to be insignificant.

GPS navigators have been widely adopted by drivers. However, due to the sensibility of GPS signals to terrain, vehicles cannot get their locations when they are inside a tunnel or on a road surrounded by high-rises where the satellite signal is blocked. This incurs the safety and convenience problems. To address the issue, we propose a novel Grid-based On-road localizaTion system (GOT), where vehicles with or without accurate GPS signals self-organize into a vehicular ad hoc network (VANET), exchange location and distance information and help each other to calculate an accurate position for all the vehicles inside the network. GOT uniquely evaluates some fuzzy geometric relationship among vehicles and employs a grid-based approach to calculate vehicle's locations, by which GOT solves the issues of lack of beacon nodes and error propagation that are the two major challenges in on-road localization. Simulation shows our GOT system is very effective and efficient in calculating the vehicular positions.

Simultaneous escape routing on dense circuit boards is a very challenging task and a great amount of manual effort is still needed in order to achieve high routability. In this paper, we present a new simultaneous escape routing algorithm which is based upon a novel boundary routing approach. Our algorithm can solve complicated escape problems in a very short time. For a set of industrial escape problems, our algorithm successfully solved all of them while Cadence Allegro PCB router was only able to complete the routing of half of the problems. In addition, we propose a clustering strategy targeting at large escape routing problems. Experimental results show that this clustering strategy can significantly cut down the runtime of our router when solving large problems.

In PCB designs, pin positions greatly affect routability of the design. State-of-the-art pin assignment algorithms are guided by simple (heuristic) metrics to estimate routability and thus have no guarantee to obtain a routable solution. In this paper, we present a novel approach to obtain a pin assignment solution that guarantees routability. We show that the problem of simultaneous pin assignment and escape routing can be solved optimally in polynomial time. We then focus on the pin assignment and escape routing for the terminals in a bus, and present algorithmic enhancements as well as discuss the tradeoffs between single-layer and multi-layer implementations. We tested our approach on a state-of-the-art industrial board with 80 buses (over 7000 nets). The pin assignment and escape routing solutions for all the 80 buses are successfully obtainted in less than 5 minutes of CPU time.

The maximum disjoint subset (MDS) of rectangles is a subset of non-overlapping rectangles with the maximum total weight. The problem of finding the MDS of general rectangles has been proven to be NP-complete in [6]. In this paper, we focus on the problem of finding the MDS of boundary rectangles, which is an open problem and is closely related to some difficult problems in PCB routing. We propose a polynomial time algorithm to optimally solve the MDS problem of boundary rectangles. Then we show that this algorithm can be applied to find the optimal solution of the bus escape routing problem.

The increasing complexity of electronic systems has made PCB layout a difficult problem. A large amount of research efforts are dedicated to the study of this problem. In this paper, we provide an overview of recent research results on the PCB layout problem. We focus on the escape routing problem and the length-matching routing problem, which are the two most important problems in PCB layout. Other relevant works are also briefly introduced.

As an important step in PCB design, the escape routing problem has been extensively studied in literature. However, few studies have been done on the escape routing of differential pairs. In this paper, we study the differential pair escape routing problem and propose two algorithms. The first one computes the optimal routing for a single differential pair while the second one is able to simultaneously route multiple differential pairs considering both routability and wire length. We then propose a two-stage routing scheme based on the two algorithms. Experimental results show that our routing scheme efficiently and effectively solves the differential pair escape routing test cases we obtained from industry.

Simultaneous escape routing on dense circuit boards is a very challenging task and great amount of manual effort is still needed in order to achieve high routability. In this paper, we present a new simultaneous escape routing algorithm which is based upon a novel boundary routing approach. Our algorithm can solve complicated escape problems in very short time. For a set of industrial escape problems, our algorithm successfully solved all of them while Cadence Allegro PCB router was only able to complete the routing of half of the problems.

Since no commercial PCB routing tools can solve the routing problem for today's complex PCBs, these circuit boards have to be routed manually, taking about 2 months of time per board. Bus planning is one of the most time-consuming steps of PCB routing. It consists of assigning buses to multiple layers of the PCB and routing them in a planar fashion on each layer. Routing congestion between on-board components and the min-max length bounds of the buses must also be considered during routing. In this paper, we present the first automatic bus planner. We tested our system on a state-of-the-art industrial circuit board with over 7000 nets and 12 signal layers. All the nets on this board were already manually routed. Our bus planner is able to achieve 100% routing completion using the layer assignment extracted from manual design. For simultaneous layer assignment and bus routing, we are able to successfully route 98.5% of the nets. The remaining 1.5% can be routed either manually or by using vias. The runtime of our bus planner is less than 3 hours on a 3 Ghz workstation.

Escape routing for packages and PCBs has been studied extensively in the past. Network flow is pervasively used to model this problem. However, none of the previous works correctly models the diagonal capacity, which is essential for 45° routing in most packages and PCBs. As a result, existing algorithms may either produce routing solutions that violate the diagonal capacity or fail to output a legal routing even though there exists one. In this paper, we propose a new network flow model that guarantees the correctness when diagonal capacity is taken into consideration. This model leads to the first optimal algorithm for escape routing. We also extend our model to handle missing pins.

Escape routing is a critical problem in PCB design. In IC-CAD'07, a layer assignment algorithm was proposed for escape routing of buses. The algorithm is optimal for single layer design in the sense that it determines if a set of buses can all be escaped on one layer. If they cannot, the algorithm is able to select a maximum subset of the buses that can be escaped on one layer. This, in turn, leads to a heuristic for the layer assignment problem with multiple layers, which is to repeatedly assign a maximum subset of the unassigned buses to a new layer. In this work, we present an algorithm that solves the multi-layer layer assignment problem optimally. Our algorithm guarantees to produce a layer assignment with minimum number of layers. We applied our algorithm on industrial data and obtained encouraging results.

Hierarchical architectures are more and more widely adopted for organizing wireless sensor networks. In such architectures, middle-tier nodes take important roles, and preventing a malicious node from impersonating a middle-tier node and injecting falsified messages becomes critical. In this paper, we propose an energy efficient, distributed scheme to secure the multicast messages from the middle-tier nodes. Our scheme does not require a priori knowledge about the hierarchical relation between middle-tier nodes and lowest-tier nodes, and is adaptive to changes of this relation. Extensive simulations are conducted to evaluate our scheme, and the results show that the scheme is energy efficient.

Length-constrained routing is a very important issue for printed circuit board (PCB) routing. Previous length-constrained routers all have assumptions on the routing topology, whereas practical designs may be free of any topological constraint. In this paper, we propose a routing scheme that deals with general topology. Unlike previous works, our approach does not impose any restriction on the routing topology. Moreover, our routing scheme is gridless. Its performance does not depend on the routing grid size of the input while the routers in the papers of Ozdal and Wong and Kubo do. This is a big advantage because modern PCB routing configurations usually imply huge routing grids. The novelty of this work is that we view the length-constrained routing problem as an area assignment problem and use a placement structure, which is the bounded-sliceline grid, to help transform the area assignment problem into a mathematical programming problem. We then use an iterative approach to solve this mathematical programming problem. Experimental results show that our routing scheme can handle practical designs that previous routers cannot handle. For designs that they could handle, our router runs much faster. For example, in one of our data, we obtain the result in 88 s while the Lagrangian relaxation based router by Ozdal and Wong takes more than one day.

Previous works on PCB bus routing assume matched pin ordering on both sides. But in practice, the pin ordering might be mismatched and the nets become twisted. In this article, we propose a preprocessing step to untangle such twisted nets. We also introduce a practical routing style, which we call single-detour routing , to simplify the untangling problem. We then present a necessary and sufficient condition for the existence of single-detour routing solutions. Furthermore, we present a dynamic-programming-based algorithm to solve the single-detour untangling problem with consideration of wire capacity between adjacent pins. Our algorithm produces an optimal single-detour routing solution that rematches the pin ordering. By integrating our algorithm into the bus router in a previous length-matching router, we show that many routing problems that cannot be solved previously can now be solved with insignificant increase in runtime.

Length-matching routing is a very important issue for PCB routing. Previous length-matching routers [1]–[3] all have assumptions on the routing topology whereas practical designs may be free of any topological constraint. In this paper, we propose a router that deals with general topology. Unlike previous routers, our router does not impose any restriction on the routing topology. Moreover, our router is gridless. Its performance does not depend on the routing grid size of the input while routers in [1]–[3] do. This is a big advantage because modern PCB routing configurations usually imply huge routing grids. The novelty of this work is that we view the lengthmatching routing problem as an area assignment problem and use a placement structure, Bounded-Sliceline Grid (BSG) [4], to help solving the problem. Experimental results show that our router can handle practical designs that previous routers can’t handle. For designs that they could handle, our router runs much faster. For example, in one of our data, we obtain the result in 88 seconds while the router in [3] takes more than one day.

How to estimate the shortest routing length when certain blocks are considered as routing obstacles is becoming an essential problem for block placement because HPWL, is no longer valid in this case. Although this problem is well studied in computational geometry (Mitchell, 2000), the research results are neither well-known to the CAD community nor presented in a way easy for CAD researchers to ultilize their establishment. With the help of some recent notions in block placement, this paper interprets the research result in Atallah and Chen (1991) and de Rezende et al. (1985), which gives the best algorithm for this problem as we know, in a way more concise and more friendly to CAD researchers. Besides, we also tailor its algorithm to VLSI CAD application. As the result, we present a method that estimates the shortest obstacle-avoiding routing length in 0(M2+ N) time for a placement with M blocks and N 2-pin nets.

The PCB routing problem has become so difficult that no commercial CAD software can provide an automatic solution for high-end boards. Existing algorithms for escape routing, an important step in PCB routing, are net-centric. Directly applying these algorithms will result in mixing nets of different buses together. But in practice, it is preferred to bundle together nets in a bus. Thus the bus-centric escape routing problem can be naturally divided into two subproblems: (1) finding a subset of buses that can be routed on the same layer without net mixings and crossings, which we refer to as the bus sequencing problem, and (2) finding the escape routing solutions for each chosen bus, which can be solved by a net-centric escape router. In this paper, we solve the bus sequencing problem. We introduce a new optimization problem called the longest common interval Sequence (LCIS) problem and model the bus sequencing problem as an LCIS problem. By using dynamic programming and balanced search tree data structure, we present an LCIS algorithm which can find an optimal solution in O(n log n) time. We also show that O(n log n) is a lower-bound for this problem and thus the time complexity of our algorithm is also the best possible.

Previous works [1], [2] on PCB bus routing assume matched pin ordering for both sides. But in practice, the pin ordering might be mismatched and the nets become twisted. In this paper, we propose a preprocessing step to untangle such twisted nets. We also present an algorithm to solve this untangling problem. Our algorithm produces an optimal singledetour routing scheme that rematches the pin ordering. By integrating our preprocessing step into the bus router in [2], we show that many routing problems that cannot be solved previously can now be solved with insignificant increase in runtime.

The recent hierarchical design framework[8] for 3D floorplan-ning suggests a better performance than previous flat design framework. Under this framework, the layer assignment of the blocks is accomplished by some partitioning algorithms which are assumed to be critical[8]. In this paper, we provide an empirical study on the impact of such partitioning algorithms on the total wire length. By generating various partitions and running our floorplanner based on these partitions, we obtain the statistic of the resultant wire length. We observe that when the design instance has a large number of blocks which are uniformly sized, different partitions with the same cut size lead to roughly the same wire length. By another experiment, we find out that the cut size of the partition has the major influence on the wire length. Therefore, we argue that cut size is a metric good enough for the wire length optimization of 3D floorplanning and suggest that future research focus on other problems such as thermal effect, signal delay, etc.

The wire length estimation is the bottleneck of packing based block placers. To cope with this problem, we present a fast wire length estimation method in this paper. The key idea is to bundle the 2-pin nets between block pairs, and measure the wire length bundle by bundle, instead of net by net. Previous bundling method [5] introduces a huge error which compromises the performance. We present an errorfree bundling approach which utilizes the piecewise linear wire length function of a pair of blocks. With the function implemented into a lookup table, the wire length can be computed promptly and precisely by binary search. Furthermore, we show that 3-pin nets can also be bundled, resulting in a further speedup. The effectiveness of our method is verified by experiments.

A non-Manhattan Hexagon/Triangle Placement (HTP for short) paradigm is proposed in the present paper. Main feature of this paradigm lies in adapting to the Y- architecture which is one of the promising non-Manhattan VLSI circuit layout architectures. Aim of the HTP is to place a set of equilateral triangles with given size onto a hexagonal chip with maximal chip area usage. Based on the O-tree representation, some adaptive packing rules are adopted to develop an effective placement algorithm for solving the HTP problem in BBL mode. Two examples with benchmark data transformed from the Manhattan BBL mode placement (ami33/49) are presented to justify the feasibility and effectiveness of our algorithms. Experiment results demonstrate that the chip area usage of 94% is achieved through simulated annealing optimization.