-
The signaling dimension of two-dimensional and polytopic systems
Authors:
Shuriku Kai,
Michele Dall'Arno
Abstract:
The signaling dimension of any given physical system represents its classical simulation cost, that is, the minimum dimension of a classical system capable of reproducing all the input/output correlations of the given system. The signaling dimension landscape is vastly unexplored; the only non-trivial systems whose signaling dimension is known -- other than quantum systems -- are the octahedron an…
▽ More
The signaling dimension of any given physical system represents its classical simulation cost, that is, the minimum dimension of a classical system capable of reproducing all the input/output correlations of the given system. The signaling dimension landscape is vastly unexplored; the only non-trivial systems whose signaling dimension is known -- other than quantum systems -- are the octahedron and the composition of two squares.
Building on previous results by Matsumoto, Kimura, and Frenkel, our first result consists of deriving bounds on the signaling dimension of any system as a function of its Minkowski measure of asymmetry. We use such bounds to prove that the signaling dimension of any two-dimensional system (i.e. with two-dimensional set of admissible states, such as polygons and the real qubit) is two if and only if such a set is centrally symmetric, and three otherwise, thus conclusively settling the problem of the signaling dimension for such systems.
Guided by the relevance of symmetries in the two dimensional case, we propose a branch and bound division-free algorithm for the exact computation of the symmetries of any given polytope, in polynomial time in the number of vertices and in factorial time in the dimension of the space. Our second result then consist of providing an algorithm for the exact computation of the signaling dimension of any given system, that outperforms previous proposals by exploiting the aforementioned bounds to improve its pruning techniques and incorporating as a subroutine the aforementioned symmetries-finding algorithm. We apply our algorithm to compute the exact value of the signaling dimension for all rational Platonic, Archimedean, and Catalan solids, and for the class of hyper-octahedral systems up to dimension five.
△ Less
Submitted 24 July, 2024;
originally announced July 2024.
-
Benchmarking End-To-End Performance of AI-Based Chip Placement Algorithms
Authors:
Zhihai Wang,
Zijie Geng,
Zhaojie Tu,
Jie Wang,
Yuxi Qian,
Zhexuan Xu,
Ziyan Liu,
Siyuan Xu,
Zhentao Tang,
Shixiong Kai,
Mingxuan Yuan,
Jianye Hao,
Bin Li,
Yongdong Zhang,
Feng Wu
Abstract:
The increasing complexity of modern very-large-scale integration (VLSI) design highlights the significance of Electronic Design Automation (EDA) technologies. Chip placement is a critical step in the EDA workflow, which positions chip modules on the canvas with the goal of optimizing performance, power, and area (PPA) metrics of final chip designs. Recent advances have demonstrated the great poten…
▽ More
The increasing complexity of modern very-large-scale integration (VLSI) design highlights the significance of Electronic Design Automation (EDA) technologies. Chip placement is a critical step in the EDA workflow, which positions chip modules on the canvas with the goal of optimizing performance, power, and area (PPA) metrics of final chip designs. Recent advances have demonstrated the great potential of AI-based algorithms in enhancing chip placement. However, due to the lengthy workflow of chip design, the evaluations of these algorithms often focus on intermediate surrogate metrics, which are easy to compute but frequently reveal a substantial misalignment with the end-to-end performance (i.e., the final design PPA). To address this challenge, we introduce ChiPBench, which can effectively facilitate research in chip placement within the AI community. ChiPBench is a comprehensive benchmark specifically designed to evaluate the effectiveness of existing AI-based chip placement algorithms in improving final design PPA metrics. Specifically, we have gathered 20 circuits from various domains (e.g., CPU, GPU, and microcontrollers). These designs are compiled by executing the workflow from the verilog source code, which preserves necessary physical implementation kits, enabling evaluations for the placement algorithms on their impacts on the final design PPA. We executed six state-of-the-art AI-based chip placement algorithms on these designs and plugged the results of each single-point algorithm into the physical implementation workflow to obtain the final PPA results. Experimental results show that even if intermediate metric of a single-point algorithm is dominant, while the final PPA results are unsatisfactory. We believe that our benchmark will serve as an effective evaluation framework to bridge the gap between academia and industry.
△ Less
Submitted 2 July, 2024;
originally announced July 2024.
-
Equivariant Local Reference Frames for Unsupervised Non-rigid Point Cloud Shape Correspondence
Authors:
Ling Wang,
Runfa Chen,
Yikai Wang,
Fuchun Sun,
Xinzhou Wang,
Sun Kai,
Guangyuan Fu,
Jianwei Zhang,
Wenbing Huang
Abstract:
Unsupervised non-rigid point cloud shape correspondence underpins a multitude of 3D vision tasks, yet itself is non-trivial given the exponential complexity stemming from inter-point degree-of-freedom, i.e., pose transformations. Based on the assumption of local rigidity, one solution for reducing complexity is to decompose the overall shape into independent local regions using Local Reference Fra…
▽ More
Unsupervised non-rigid point cloud shape correspondence underpins a multitude of 3D vision tasks, yet itself is non-trivial given the exponential complexity stemming from inter-point degree-of-freedom, i.e., pose transformations. Based on the assumption of local rigidity, one solution for reducing complexity is to decompose the overall shape into independent local regions using Local Reference Frames (LRFs) that are invariant to SE(3) transformations. However, the focus solely on local structure neglects global geometric contexts, resulting in less distinctive LRFs that lack crucial semantic information necessary for effective matching. Furthermore, such complexity introduces out-of-distribution geometric contexts during inference, thus complicating generalization. To this end, we introduce 1) EquiShape, a novel structure tailored to learn pair-wise LRFs with global structural cues for both spatial and semantic consistency, and 2) LRF-Refine, an optimization strategy generally applicable to LRF-based methods, aimed at addressing the generalization challenges. Specifically, for EquiShape, we employ cross-talk within separate equivariant graph neural networks (Cross-GVP) to build long-range dependencies to compensate for the lack of semantic information in local structure modeling, deducing pair-wise independent SE(3)-equivariant LRF vectors for each point. For LRF-Refine, the optimization adjusts LRFs within specific contexts and knowledge, enhancing the geometric and semantic generalizability of point features. Our overall framework surpasses the state-of-the-art methods by a large margin on three benchmarks. Code and models will be publicly available.
△ Less
Submitted 1 April, 2024;
originally announced April 2024.
-
PreRoutGNN for Timing Prediction with Order Preserving Partition: Global Circuit Pre-training, Local Delay Learning and Attentional Cell Modeling
Authors:
Ruizhe Zhong,
Junjie Ye,
Zhentao Tang,
Shixiong Kai,
Mingxuan Yuan,
Jianye Hao,
Junchi Yan
Abstract:
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 indu…
▽ More
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.
△ Less
Submitted 12 March, 2024; v1 submitted 26 February, 2024;
originally announced March 2024.
-
Escaping Local Optima in Global Placement
Authors:
Ke Xue,
Xi Lin,
Yunqi Shi,
Shixiong Kai,
Siyuan Xu,
Chao Qian
Abstract:
Placement is crucial in the physical design, as it greatly affects power, performance, and area metrics. Recent advancements in analytical methods, such as DREAMPlace, have demonstrated impressive performance in global placement. However, DREAMPlace has some limitations, e.g., may not guarantee legalizable placements under the same settings, leading to fragile and unpredictable results. This paper…
▽ More
Placement is crucial in the physical design, as it greatly affects power, performance, and area metrics. Recent advancements in analytical methods, such as DREAMPlace, have demonstrated impressive performance in global placement. However, DREAMPlace has some limitations, e.g., may not guarantee legalizable placements under the same settings, leading to fragile and unpredictable results. This paper highlights the main issue as being stuck in local optima, and proposes a hybrid optimization framework to efficiently escape the local optima, by perturbing the placement result iteratively. The proposed framework achieves significant improvements compared to state-of-the-art methods on two popular benchmarks.
△ Less
Submitted 28 February, 2024;
originally announced February 2024.
-
LLM4EDA: Emerging Progress in Large Language Models for Electronic Design Automation
Authors:
Ruizhe Zhong,
Xingbo Du,
Shixiong Kai,
Zhentao Tang,
Siyuan Xu,
Hui-Ling Zhen,
Jianye Hao,
Qiang Xu,
Mingxuan Yuan,
Junchi Yan
Abstract:
Driven by Moore's Law, the complexity and scale of modern chip design are increasing rapidly. Electronic Design Automation (EDA) has been widely applied to address the challenges encountered in the full chip design process. However, the evolution of very large-scale integrated circuits has made chip design time-consuming and resource-intensive, requiring substantial prior expert knowledge. Additio…
▽ More
Driven by Moore's Law, the complexity and scale of modern chip design are increasing rapidly. Electronic Design Automation (EDA) has been widely applied to address the challenges encountered in the full chip design process. However, the evolution of very large-scale integrated circuits has made chip design time-consuming and resource-intensive, requiring substantial prior expert knowledge. Additionally, intermediate human control activities are crucial for seeking optimal solutions. In system design stage, circuits are usually represented with Hardware Description Language (HDL) as a textual format. Recently, Large Language Models (LLMs) have demonstrated their capability in context understanding, logic reasoning and answer generation. Since circuit can be represented with HDL in a textual format, it is reasonable to question whether LLMs can be leveraged in the EDA field to achieve fully automated chip design and generate circuits with improved power, performance, and area (PPA). In this paper, we present a systematic study on the application of LLMs in the EDA field, categorizing it into the following cases: 1) assistant chatbot, 2) HDL and script generation, and 3) HDL verification and analysis. Additionally, we highlight the future research direction, focusing on applying LLMs in logic synthesis, physical design, multi-modal feature extraction and alignment of circuits. We collect relevant papers up-to-date in this field via the following link: https://github.com/Thinklab-SJTU/Awesome-LLM4EDA.
△ Less
Submitted 28 December, 2023;
originally announced January 2024.
-
Real-time Path Planning of Driver-less Mining Trains with Time-dependent Physical Constraints
Authors:
Xiaojiang Ren,
Hui Guo,
Sheng Kai,
Guoqiang Mao
Abstract:
While the increased automation levels of production and operation equipment have led to improved productivity of mining activity in open pit mines, the capacity of mine transport system become a bottleneck. The optimization of mine transport system is of great practical significance to reduce the production and operation cost and improve the production and organizational efficiency of mines. In th…
▽ More
While the increased automation levels of production and operation equipment have led to improved productivity of mining activity in open pit mines, the capacity of mine transport system become a bottleneck. The optimization of mine transport system is of great practical significance to reduce the production and operation cost and improve the production and organizational efficiency of mines. In this paper we first formulate a multi-objective optimisation problem for mine railway scheduling by introducing a set of mathematical constraints. As the problem is NP-hard, we then devise a Mixed Integer Programming based solution to solve this problem, and develop an online framework accordingly. We finally conduct test cases to evaluate the performance of the proposed solution. Experimental results demonstrate that the proposed solution is efficient and able to generate train schedule in a real-time manner.
△ Less
Submitted 6 January, 2023; v1 submitted 20 December, 2022;
originally announced December 2022.
-
RITA: Boost Driving Simulators with Realistic Interactive Traffic Flow
Authors:
Zhengbang Zhu,
Shenyu Zhang,
Yuzheng Zhuang,
Yuecheng Liu,
Minghuan Liu,
Liyuan Mao,
Ziqin Gong,
Shixiong Kai,
Qiang Gu,
Bin Wang,
Siyuan Cheng,
Xinyu Wang,
Jianye Hao,
Yong Yu
Abstract:
High-quality traffic flow generation is the core module in building simulators for autonomous driving. However, the majority of available simulators are incapable of replicating traffic patterns that accurately reflect the various features of real-world data while also simulating human-like reactive responses to the tested autopilot driving strategies. Taking one step forward to addressing such a…
▽ More
High-quality traffic flow generation is the core module in building simulators for autonomous driving. However, the majority of available simulators are incapable of replicating traffic patterns that accurately reflect the various features of real-world data while also simulating human-like reactive responses to the tested autopilot driving strategies. Taking one step forward to addressing such a problem, we propose Realistic Interactive TrAffic flow (RITA) as an integrated component of existing driving simulators to provide high-quality traffic flow for the evaluation and optimization of the tested driving strategies. RITA is developed with consideration of three key features, i.e., fidelity, diversity, and controllability, and consists of two core modules called RITABackend and RITAKit. RITABackend is built to support vehicle-wise control and provide traffic generation models from real-world datasets, while RITAKit is developed with easy-to-use interfaces for controllable traffic generation via RITABackend. We demonstrate RITA's capacity to create diversified and high-fidelity traffic simulations in several highly interactive highway scenarios. The experimental findings demonstrate that our produced RITA traffic flows exhibit all three key features, hence enhancing the completeness of driving strategy evaluation. Moreover, we showcase the possibility for further improvement of baseline strategies through online fine-tuning with RITA traffic flows.
△ Less
Submitted 7 December, 2023; v1 submitted 7 November, 2022;
originally announced November 2022.
-
Can rhythm be touched? An evaluation of rhythmic sketch performance with augmented multimodal feedback
Authors:
Feng Feng,
Shang Kai,
Tony Stockman
Abstract:
Although it has been shown that augmented multimodal feedback has a facilitatory effect on motor performance for motor learning and music training, the functionality of haptic feedback combined with other modalities in rhythmic movement tasks has rarely been explored and analysed. In this paper, we evaluate the functionality of visual-haptic feedback in a rhythmic sketch task by comparing it with…
▽ More
Although it has been shown that augmented multimodal feedback has a facilitatory effect on motor performance for motor learning and music training, the functionality of haptic feedback combined with other modalities in rhythmic movement tasks has rarely been explored and analysed. In this paper, we evaluate the functionality of visual-haptic feedback in a rhythmic sketch task by comparing it with other multimodal conditions. Further, we examine the possibility of accessing the quality of task execution through kinematic analysis. Based on participants' speed profiles, we investigate the quality of motor control and movement smoothness under different feedback conditions. Results revealed better motor control ability with auditory feedback and improved movement smoothness with haptic feedback. Finally, we propose that haptic feedback can be integrated with other modal stimuli for different interaction purposes, and that kinematic analysis can be a complementary approach to gesture analysis as well as providing subjective evaluation of interaction performance.
△ Less
Submitted 16 February, 2020;
originally announced February 2020.
-
Compressed Exponential Relaxation as Superposition of Dual Structure in Pattern Dynamics of Nematic Liquid Crystals
Authors:
Takayuki Narumi,
Fahrudin Nugroho,
Junichi Yoshitani,
Yoshiki Hidaka,
Masaru Suzuki,
Shoichi Kai
Abstract:
Soft-mode turbulence (SMT) is the spatiotemporal chaos observed in homeotropically aligned nematic liquid crystals, where non-thermal fluctuations are induced by nonlinear coupling between the Nambu-Goldstone and convective modes. The net and modal relaxations of the disorder pattern dynamics in SMT have been studied to construct the statistical physics of nonlinear nonequilibrium systems. The net…
▽ More
Soft-mode turbulence (SMT) is the spatiotemporal chaos observed in homeotropically aligned nematic liquid crystals, where non-thermal fluctuations are induced by nonlinear coupling between the Nambu-Goldstone and convective modes. The net and modal relaxations of the disorder pattern dynamics in SMT have been studied to construct the statistical physics of nonlinear nonequilibrium systems. The net relaxation dynamics is well-described by a compressed exponential function and the modal one satisfies a dual structure, dynamic crossover accompanied by a breaking of time-reversal invariance. Because the net relaxation is described by a weighted mean of the modal ones with respect to the wave number, the compressed-exponential behavior emerges as a superposition of the dual structure. Here, we present experimental results of the power spectra to discuss the compressed-exponential behavior and the dual structure from a viewpoint of the harmonic analysis. We also derive a relationship of the power spectra from the evolution equation of the modal autocorrelation function. The formula will be helpful to study non-thermal fluctuations in experiments such as the scattering methods.
△ Less
Submitted 30 November, 2012;
originally announced November 2012.
-
Memory function of turbulent fluctuations in soft-mode turbulence
Authors:
Takayuki Narumi,
Junichi Yoshitani,
Masaru Suzuki,
Yoshiki Hidaka,
Fahrudin Nugroho,
Tomoyuki Nagaya,
Shoichi Kai
Abstract:
Modal relaxation dynamics has been observed experimentally to clarify statistical-physical properties of soft-mode turbulence, the spatiotemporal chaos observed in homeotropically aligned nematic liquid crystals. We found a dual structure, dynamical crossover associated with violation of time-reversal invariance, the corresponding time scales satisfying a dynamical scaling law. To specify the orig…
▽ More
Modal relaxation dynamics has been observed experimentally to clarify statistical-physical properties of soft-mode turbulence, the spatiotemporal chaos observed in homeotropically aligned nematic liquid crystals. We found a dual structure, dynamical crossover associated with violation of time-reversal invariance, the corresponding time scales satisfying a dynamical scaling law. To specify the origin of the dual structure, the memory function due to non-thermal fluctuations has been defined by a projection-operator method and obtained numerically using experimental results. The results of the memory function suggest that the non-thermal fluctuations can be divided into Markov and non-Markov contributions, the latter is called the turbulent fluctuation (TF). Consequently, the relaxation dynamics is separated into three characteristic stages: bare-friction, early, and late stages. If the dissipation due to TFs dominates over that of the Markov contribution, the bare-friction stage contracts; the early and late stages then configure the dual structure. The memory effect due to TFs results in the time-reversible relaxation at the early stage, and the disappearance of the memory by turbulent mixing leads to a simple exponential relaxation at the late stage. Furthermore, the memory effect due to TFs is shown to originate from characteristic spatial coherency called the patch structure.
△ Less
Submitted 20 January, 2013; v1 submitted 28 October, 2012;
originally announced October 2012.
-
Glassy dynamics in relaxation of soft-mode turbulence
Authors:
Fahrudin Nugroho,
Takayuki Narumi,
Yoshiki Hidaka,
Junichi Yoshitani,
Masaru Suzuki,
Shoichi Kai
Abstract:
The autocorrelation function of pattern fluctuation is used to study soft-mode turbulence (SMT), a spatiotemporal chaos observed in homeotropic nematics. We show that relaxation near the electroconvection threshold deviates from the exponential. To describe this relaxation, we propose a compressed exponential appearing in dynamics of glass forming liquids. Our findings suggest that coherent motion…
▽ More
The autocorrelation function of pattern fluctuation is used to study soft-mode turbulence (SMT), a spatiotemporal chaos observed in homeotropic nematics. We show that relaxation near the electroconvection threshold deviates from the exponential. To describe this relaxation, we propose a compressed exponential appearing in dynamics of glass forming liquids. Our findings suggest that coherent motion contributes to SMT dynamics. We also confirmed that characteristic time is inversely proportional to electroconvection's control parameter.
△ Less
Submitted 15 February, 2012;
originally announced February 2012.
-
Size Dependence of Current-Voltage Properties in Coulomb Blockade Networks
Authors:
Takayuki Narumi,
Masaru Suzuki,
Yoshiki Hidaka,
Shoichi Kai
Abstract:
We theoretically investigate the current-voltage (I-V) property of two-dimensional Coulomb blockade (CB) arrays by conducting Monte Carlo simulations. The I-V property can be divided into three regions and we report the dependence of the aspect ratio delta (namely, the lateral size N_{y} over the longitudinal one N_{x}). We show that the average CB threshold obeys a power-law decay as a function o…
▽ More
We theoretically investigate the current-voltage (I-V) property of two-dimensional Coulomb blockade (CB) arrays by conducting Monte Carlo simulations. The I-V property can be divided into three regions and we report the dependence of the aspect ratio delta (namely, the lateral size N_{y} over the longitudinal one N_{x}). We show that the average CB threshold obeys a power-law decay as a function of delta. Its exponent gamma corresponds to a sensitivity of the threshold depending on delta, and is inversely proportional to N_{x} (i.e., delta at fixed N_{y}). Further, the power-law exponent zeta, characterizing the nonlinearity of the I-V property in the intermediate region, logarithmically increases as delta increases. Our simulations describe the experimental result zeta=2.25 obtained by Parthasarathy et al. [Phys. Rev. Lett. 87 (2001) 186807]. In addition, the asymptotic I-V property of one-dimensional arrays obtained by Bascones et al. [Phys. Rev. B. 77 (2008) 245422] is applied to two-dimensional arrays. The asymptotic equation converges to the Ohm's law at the large voltage limit, and the combined tunneling-resistance is inversely proportional to delta. The extended asymptotic equation with the first-order perturbation well describes the experimental result obtained by Kurdak et al. [Phys. Rev. B 57 (1998) R6842]. Based on our asymptotic equation, we can estimate physical values that it is hard to obtain experimentally.
△ Less
Submitted 1 September, 2011;
originally announced September 2011.
-
Active Brownian Motion in Threshold Distribution of a Coulomb Blockade Model
Authors:
Takayuki Narumi,
Masaru Suzuki,
Yoshiki Hidaka,
Tetsuya Asai,
Shoichi Kai
Abstract:
Randomly-distributed offset charges affect the nonlinear current-voltage property via the fluctuation of the threshold voltage of Coulomb blockade arrays. We analytically derive the distribution of the threshold voltage for a model of one-dimensional locally-coupled Coulomb blockade arrays, and propose a general relationship between conductance and the distribution. In addition, we show the distri…
▽ More
Randomly-distributed offset charges affect the nonlinear current-voltage property via the fluctuation of the threshold voltage of Coulomb blockade arrays. We analytically derive the distribution of the threshold voltage for a model of one-dimensional locally-coupled Coulomb blockade arrays, and propose a general relationship between conductance and the distribution. In addition, we show the distribution for a long array is equivalent to the distribution of the number of upward steps for aligned objects of different height. The distribution satisfies a novel Fokker-Planck equation corresponding to active Brownian motion. The feature of the distribution is clarified by comparing it with the Wigner and Ornstein-Uhlenbeck processes. It is not restricted to the Coulomb blockade model, but instructive in statistical physics generally.
△ Less
Submitted 19 September, 2011; v1 submitted 23 June, 2011;
originally announced June 2011.
-
Nonsteady condensation and evaporation waves
Authors:
Osamu Inomoto,
Shoichi Kai,
Boris Malomed
Abstract:
We study motion of a phase transition front at a constant temperature between stable and metastable states in fluids with the universal Van der Waals equation of state (which is valid sufficiently close to the fluid's critical point). We focus on a case of relatively large metastability and low viscosity, when it can be shown analytically that no steadily moving phase-transition front exists. Nu…
▽ More
We study motion of a phase transition front at a constant temperature between stable and metastable states in fluids with the universal Van der Waals equation of state (which is valid sufficiently close to the fluid's critical point). We focus on a case of relatively large metastability and low viscosity, when it can be shown analytically that no steadily moving phase-transition front exists. Numerically simulating a system of the one-dimensional Navier-Stokes and continuity equations, we find that, in this case, the nonsteady phase-transition front emits acoustic shocks in forward and backward directions. Through this mechanism, the front drops its velocity and eventually comes to a halt. The acoustic shock wave may shuttle, bouncing elastically from the system's edge and strongly inelastically from the phase transition front. Nonsteady rarefaction shock waves appear in the shuttle process, despite the fact that the model does not admit steady rarefaction waves propagating between stationary states. If the viscosity is below a certain threshold, an instability sets in, driving the system into a turbulent state. This work was supported by the Japan Society for Promotion of Science.
△ Less
Submitted 11 June, 2000;
originally announced June 2000.