The recent success of Shampoo in the AlgoPerf contest has sparked renewed interest in Kronecker-factorization-based optimization algorithms for training neural networks. Despite its success, Shampoo relies heavily on several heuristics such as learning rate grafting and stale preconditioning to achieve performance at-scale. These heuristics increase algorithmic complexity, necessitate further hyperparameter tuning, and lack theoretical justification. This paper investigates these heuristics from the angle of Frobenius norm approximation to full-matrix Adam and decouples the preconditioner's eigenvalues and eigenbasis updates. We show that grafting from Adam mitigates the staleness and mis-scaling of the preconditioner's *eigenvalues* and how correcting the eigenvalues directly eliminates the need for learning rate grafting. To manage the error induced by infrequent *eigenbasis* computations, we propose an adaptive criterion for determining the eigenbasis computation frequency motivated by terminating a warm-started QR algorithm. This criterion decouples the update frequency of different preconditioner matrices and enables us to investigate the impact of approximation error on convergence. These practical techniques offer a principled angle towards removing Shampoo's heuristics and developing improved Kronecker-factorization-based training algorithms.

Since a Chinese syllable can correspond to many characters (homophones), the syllable-to-character conversion task is quite challenging for Chinese phonetic input methods (CPIM). There are usually two stages in a CPIM: 1. segment the syllable sequence into syllable words, and 2. select the most likely character words for each syllable word. A CPIM usually assumes that the input is a complete sentence, and evaluates the performance based on a well-formed corpus. However, in practice, most Pinyin users prefer progressive text entry in several short chunks, mainly in one or two words each (most Chinese words consist of two or more characters). Short chunks do not provide enough contexts to perform the best possible syllable-to-character conversion, especially when a chunk consists of overlapping syllable words. In such cases, a conversion system often selects the boundary of a word with the highest frequency. Short chunk input is even more popular on platforms with limited computing power, such as mobile phones. Based on the observation that the relative strength of a word can be quite different when calculated leftwards or rightwards, we propose a simple division of the word context into the left context and the right context. Furthermore, we design a double ranking strategy for each word to reduce the number of errors in Step 1. Our strategy is modeled as the minimum feedback arc set problem on bipartite tournament with approximate solutions derived from genetic algorithm. Experiments show that, compared to the frequency-based method (FBM) (low memory and fast) and the conditional random fields (CRF) model (larger memory and slower), our double ranking strategy has the benefits of less memory and low power requirement with competitive performance. We believe a similar strategy could also be adopted to disambiguate conflicting linguistic patterns effectively.

In this paper we study a global routing problem that considers not only overflow and wirelength but also layer directives. A layer directive is often given to a timing-critical net for meeting target performance, and it specifies a range of consecutive layers on which the net should be routed. Unlike a previous work that focuses only on a restricted set of layer ranges, our problem allows arbitrary layer ranges to be specified. We present a global router which enhances an academic router by employing techniques to take general layer directives into account during two-dimensional (2D) routing and layer assignment. The experiment results show that our global router can produce encouraging solutions for all test cases.

For more than thirty years, the parallel programming community has used the dependence graph as the main abstraction for reasoning about and exploiting parallelism in "regular" algorithms that use dense arrays, such as finite-differences and FFTs. In this paper, we argue that the dependence graph is not a suitable abstraction for algorithms in new application areas like machine learning and network analysis in which the key data structures are "irregular" data structures like graphs, trees, and sets.

Global routing is a very crucial stage in a design cycle, because it physically plans the routes of nets on a chip. In order to boost the research and development of global routing techniques, ISPD held contests and released benchmarks in 2007 and 2008, respectively. However, the contests may lead researchers away from facing other real problems in practice. In this paper we study a new global routing problem that not only considers traditional routing objectives such as overflow and wirelength but also focuses on honoring layer directives that are usually specified for timing-critical nets to alleviate performance degrading. Based on novel extensions of an academic router, we present a new global router called GLADE for the addressed problem. The experimental results show that GLADE can effectively generate a high-quality solution, which balances the metrics under consideration, for each test case from the set of recently released ICCAD 2009 benchmarks.

Antenna effect is an important issue that needs to be considered in the routing stage for modern design. In this paper, we study a layer assignment problem that arises during multi-layer global routing and takes antenna avoidance into account. The problem asks to transform a given 2-dimensional global routing result into a 3-dimensional one (i.e., a multi-layer one) and to minimize the amount of antenna violations and the via count subject to given wire congestion constraints. We present an algorithm that tackles the addressed layer assignment problem in a net-by-net manner. An existing dynamic-programming-based single-net layer assignment method that can only consider the via count is judiciously modified and adopted by our algorithm to handle both antenna avoidance and via count minimization for each net. To further reduce the via count but without increasing the amount of antenna violations, a refinement procedure based on min-cost max-flow is developed and added to our algorithm. The experiment results show that when compared with the layer assignment approach adopted by a state-of-the-art academic global router, our algorithm not only can improve the via count slightly but also can significantly reduce the amount of antenna violations.

In this paper, we study a layer assignment problem which arises during multi-layer global routing. Our layer assignment problem takes the total wire overflow and the maximum wire overflow of a given 2D global routing solution to form the wire congestion constraints, and asks to find a 3D counterpart through layer assignment such that the total via overflow and the total via count of the 3D result are both as small as possible while the wire congestion constraints are satisfied. To solve this layer assignment problem, we present an algorithm which first determines a net order, then applies a dynamic programming technique to perform layer assignment in a net-by-net manner according to the net order, and finally refines the solution iteratively until convergence. Our algorithm is guaranteed to always generate a layer assignment solution satisfying the wire congestion constraints. We tested our layer assignment algorithm on the ISPD'07 and ISPD'08 benchmarks and the results are very encouraging.

In this paper, we study the problem of layer assignment for via minimization, which arises during multilayer global routing. In addressing this problem, we take the total overflow and the maximum overflow as the congestion constraints from a given one-layer global routing solution and aim to find a layer assignment result for each net such that the via cost is minimized while the given congestion constraints are satisfied. To solve the problem, we propose a polynomial-time algorithm which first generates a net order and then performs layer assignment one net at a time according to the order using dynamic programming. Our algorithm is guaranteed to generate a layer assignment solution satisfying the given congestion constraints. We used the six-layer benchmarks released from the ISPD'07 global routing contest to test our algorithm. The experimental results show that our algorithm was able to improve the contest results of the top three winners MaizeRouter, BoxRouter, and FGR on each benchmark. As compared to BoxRouter 2.0 and FGR 1.1, which are newer versions of BoxRouter and FGR, our algorithm respectively produced smaller via costs on all benchmarks and half the benchmarks. Our algorithm can also be adapted to refine a given multilayer global routing solution in a net-by-net manner, and the experimental results show that this refinement approach improved the via costs on all benchmarks for FGR 1.1.