Floating-point arithmetic is widely used in high-precision computing fields such as national defense, aerospace, and finance. Different applications have varying requirements for floating-point computation precision, and how to maximize program performance while meeting precision requirements is a crucial challenge in high-performance program design. Mixed-precision technology is a common optimization strategy to address this issue, which involves using multiple precision types within the same program. However, most existing research on mixed precision tends to fall into local optima and fails to directly provide users with usable mixed-precision programs. Since genetic algorithms are optimization methods with global search capabilities, we propose a genetic algorithm-based mixed-precision tuning method and develop a tool called GATUNER. Specifically, GATUNER first analyzes the variables and statements of the program to construct a dependency graph of the program. Then, it uses the Leiden algorithm to detect community structures in the dependency graph, employs an improved genetic algorithm to search for mixed-precision configurations, and finally automatically generates the corresponding mixed-precision program. We evaluated GATUNER on 14 benchmark tests and application programs. The experimental results show that GATUNER can find valid mixed-precision configurations for 76.79% of the test programs, with an average performance improvement of 31.65% for the found mixed-precision configurations. Compared with HIFPTUNER, ADAPT, and CHEF-FP, the average performance improvement of the mixed-precision configurations found by GATUNER increased by 14.1%, 24.09%, and 15.18% respectively. In addition, compared with PESA, the average performance improvement of the mixed-precision configurations obtained by GATUNER increased by 18.67%.

General Matrix Multiplication (GEMM) is a fundamental operation in high-performance computing and artificial intelligence, with its performance directly impacting the overall efficiency of higher-level applications. This paper optimizes GEMM by leveraging the characteristics of the RISC-V architecture, achieving significant performance improvements on the XuanTie C908 and C910 processors. It is also observed that traditional optimization method become a bottleneck for small-scale GEMM performance on RISC-V. To address this, we propose an analytical model-based approach that effectively enhances small-scale GEMM performance. In performance evaluation, we tested square matrices and irregular matrices (derived from convolutional neural networks) to validate the optimized GEMM across various scenarios and assess its performance in realworld applications. Compared to the GEMM routines in popular open-source BLAS (Basic Linear Algebra Subprograms) libraries (OpenBLAS and BLIS), the optimized GEMM achieves average speedups of$1.29 \times$and$2.20 \times$, with maximum speedups of$6.51 \times$and$27.85 \times$on the C908 platform. On the C910 platform, the average speedups are$2.38 \times$and$5.15 \times$, with maximum speedups of$17.15 \times$and$84.16 \times$.

Understanding how transformers learn and utilize hidden connections between tokens is crucial to understand the behavior of large language models. To understand this mechanism, we consider the task of two-mixture of linear classification which possesses a hidden correspondence structure among tokens, and study the training dynamics of a symmetric two-headed transformer with ReLU neurons. Motivated by the stage-wise learning phenomenon in our experiments, we design and theoretically analyze a three-stage training algorithm, which can effectively characterize the actual gradient descent dynamics when we simultaneously train the neuron weights and the softmax attention. The first stage is a neuron learning stage, where the neurons align with the underlying signals. The second stage is a attention feature learning stage, where we analyze the feature learning process of how the attention learns to utilize the relationship between the tokens to solve certain hard samples. In the meantime, the attention features evolve from a nearly non-separable state (at the initialization) to a well-separated state. The third stage is a convergence stage, where the population loss is driven towards zero. The key technique in our analysis of softmax attention is to identify a critical sub-system inside a large dynamical system and bound the growth of the non-linear sub-system by a linear system. Finally, we discuss the setting with more than two mixtures. We empirically show the difficulty of generalizing our analysis of the gradient flow dynamics to the case even when the number of mixtures equals three, although the transformer can still successfully learn such distribution. On the other hand, we show by construction that there exists a transformer that can solve mixture of linear classification given any arbitrary number of mixtures.

Floating-point error detection is crucial in numerical computing, particularly for multi-parameter functions where even minor errors can propagate and significantly impact results. The sparse distribution of floating-point errors poses a significant detection challenge, as significant deviations are triggered by only rare inputs. Existing search algorithms face two major limitations: poor scalability for multi-parameter functions and insufficient utilization of floating-point representation characteristics. To address these challenges, we propose SDPS (Scalable Detection via Parallel Subdomain Search), a novel algorithm that combines adaptive domain partitioning with floating-point-specific heuristics. SDPS employs a multi-level error classification system and specialized point generation strategies, supported by efficient parallel processing through dynamic task allocation. Our comprehensive evaluation demonstrates that SDPS significantly outperforms state-of-the-art methods in both detection accuracy and computational efficiency, especially for multi-parameter functions where it effectively addresses the exponential growth of search space that limits existing approaches.

It has been observed that applying pruning-at-initialization methods and training the sparse networks can sometimes yield slightly better test performance than training the original dense network. Such experimental observations are yet to be understood theoretically. This work makes the first attempt to study this phenomenon. Specifically, we identify a theoretical minimal setting and study a classification task with a one-hidden-layer neural network, which is randomly pruned according to different rates at the initialization. We show that as long as the pruning rate is below a certain threshold, the network provably exhibits good generalization performance after training.More surprisingly, the generalization bound gets better as the pruning rate mildly gets larger. To complement this positive result, we also show a negative result: there exists a large pruning rate such that while gradient descent is still able to drive the training loss toward zero, the generalization performance is no better than random guessing. This further suggests that pruning can change the feature learning process, which leads to the performance drop of the pruned neural network. To our knowledge, this is the first theory work studying how different pruning rates affect neural networks' performance, suggesting that an appropriate pruning rate might improve the neural network's generalization.

Quantum compilers play an essential role in the translation of quantum algorithms on quantum hardware. As the size of quantum programs increases, the problem of extreme compilation overhead becomes apparent. To address this problem, compilation frameworks with high-level intermediate representations such as QCOR have been introduced. However, these frameworks still face significant overhead from qubit mapping and optimizing sequence redundancy, resulting in challenges when compiling circuits to realistic hardware. In our paper, a low-cost optimizing compiler (LCOC) is proposed, which addresses the overhead in qubit mapping and enhanced the optimization capabilities. A qubit mapping optimizer based on the LLVM Polly is introduced in LCOC, which implements an efficient mapping of quantum programs containing specific loop types. While achieving low-cost mapping, it considerably reduces the depth of the circuit. We also implement an optimization sequence generator that leverages the modularity of LLVM and iterative compilation to provide LCOC with a more flexible and efficient optimization sequence. We conduct experiments with 100+ qubit circuits. Experiments show that LCOC is up to 1540× faster compared to Qiskit and 74× faster compared to QCOR in compile time. The average speedup relative to Qiskit and QCOR are 194× and 8.64×, respectively. In addition, it can effectively reduce the circuit depth by 50.32% compared to Qiskit and 83.5% compared to QCOR on average.

We introduce a floating-point (FP) error optimization approach called Arfa that partitions the domain D of an FP expression fe into regimes and rewrites fe in each regime where fe shows larger errors. First, Arfa seeks a rewrite substitution fo with lower errors across D, whose error distribution is plotted for effective regime inference. Next, Arfa generates an incomplete set of ordered rewrite candidates within each regime of interest, so that searching for the best rewrite substitutions is performed efficiently. Finally, Arfa selects the best rewrite substitution by inspecting the errors of top ranked rewrite candidates, with enhancing precision also considered. Experiments on 56 FPbench examples and four real-life programs show that Arfa not only reduces the maximum and average errors of fe by 4.73 and 2.08 bits on average (and up to 33 and 16 bits), but also exhibits lower errors, sometimes to a significant degree, than Herbie and NumOpt.

Understanding the training dynamics of transformers is important to explain the impressive capabilities behind large language models. In this work, we study the dynamics of training a shallow transformer on a task of recognizing co-occurrence of two designated words. In the literature of studying training dynamics of transformers, several simplifications are commonly adopted such as weight reparameterization, attention linearization, special initialization, and lazy regime. In contrast, we analyze the gradient flow dynamics of simultaneously training three attention matrices and a linear MLP layer from random initialization, and provide a framework of analyzing such dynamics via a coupled dynamical system. We establish near minimum loss and characterize the attention model after training. We discover that gradient flow serves as an inherent mechanism that naturally divide the training process into two phases. In Phase 1, the linear MLP quickly aligns with the two target signals for correct classification, whereas the softmax attention remains almost unchanged. In Phase 2, the attention matrices and the MLP evolve jointly to enlarge the classification margin and reduce the loss to a near minimum value. Technically, we prove a novel property of the gradient flow, termed \textit{automatic balancing of gradients}, which enables the loss values of different samples to decrease almost at the same rate and further facilitates the proof of near minimum training loss. We also conduct experiments to verify our theoretical results.

We study training one-hidden-layer ReLU networks in the neural tangent kernel (NTK) regime, where the networks' biases are initialized to some constant rather than zero. We prove that under such initialization, the neural network will have sparse activation throughout the entire training process, which enables fast training procedures via some sophisticated computational methods. With such initialization, we show that the neural networks possess a different limiting kernel which we call bias-generalized NTK, and we study various properties of the neural networks with this new kernel. We first characterize the gradient descent dynamics. In particular, we show that the network in this case can achieve as fast convergence as the dense network, as opposed to the previous work suggesting that the sparse networks converge slower. In addition, our result improves the previous required width to ensure convergence. Secondly, we study the networks' generalization: we show a width-sparsity dependence, which yields a sparsity-dependent Rademacher complexity and generalization bound. To our knowledge, this is the first sparsity-dependent generalization result via Rademacher complexity. Lastly, we study the smallest eigenvalue of this new kernel. We identify a data-dependent region where we can derive a much sharper lower bound on the NTK's smallest eigenvalue than the worst-case bound previously known. This can lead to improvement in the generalization bound.

Motivated by both theory and practice, we study how random pruning the weights affects a neural network’s neural tangent kernel (NTK). In particular, this work establishes an equivalence of the NTKs between a fully-connected neural network and its randomly pruned version. The equivalence is established under two cases. The first main result studies the infinite-width asymptotic. It is shown that given a pruning probability, for fully-connected neural networks with the weights randomly pruned at the initialization, as the width of each layer grows to infinity sequentially, the NTK of the pruned neural network converges to the limiting NTK of the original network with some extra scaling. If the network weights are rescaled appropriately after pruning, this extra scaling can be removed. The second main result considers the finite width case. It is shown that to ensure the NTK’s closeness to the limit, the dependence of width on the sparsity parameter is asymptotically linear, as the NTK’s gap to its limit goes down to zero. Moreover, if the pruning probability is set to zero (i.e., no pruning), the bound on the required width matches the bound for fully-connected neural networks in previous works up to logarithmic factors. The proof of this result requires developing novel analysis of a network structure which we called mask-induced pseudo-networks.Experiments are provided to evaluate our results.

Mixed-precision tuning is a valuable approach for striking a balance between the accuracy and performance of floating-point computations. However, selecting suitable configurations from numerous mixed-precision configurations can be challenging. The discrete and finite nature of floating-point numbers introduces unavoidable rounding errors that are difficult to predict. To address these challenges, we propose an accuracy gain evaluation function for expressions. This evaluation function quantifies the extent of accuracy improvement achieved by adjusting the precision of the operations within the expression. This is achieved through a thorough examination of the impact of each operation's condition number and implementation error on the final error. Based on this evaluation function, we present AMPT, a mixed-precision tuning method specifically for expressions. AMPT not only identifies the optimal mixed-precision configuration but also automatically generates the corresponding code. Experimental results demonstrate that AMPT accurately assesses the accuracy gains of different mixed-precision configurations, and the mixed-precision code generated by AMPT can achieve low-error computation of expressions with low performance overhead.

Existing search heuristics used to find input values that result in significant floating-point (FP) errors or small ranges that cover them are accompanied by severe constraints, complicating their implementation and restricting their general applicability. This paper introduces an error analysis tool called Eiffel to infer error-inducing input ranges instead of searching them. Given an FP expression with its domain$\mathcal{D}$, Eiffel first constructs an error data set by sampling values across a smaller domain$\mathcal{R}$and assembles these data into clusters. If more than two clusters are formed, Eiffel derives polynomial curves that best fit the bound coordinates of the error-inducing ranges in$\mathcal{R}$, extrapolating them to infer all target ranges of$\mathcal{D}$and reporting the maximal error. Otherwise, Eiffel simply returns the largest error across$\mathcal{R}$. Experimental results show that Eiffel exhibits a broader applicability than Atomu and$\mathbf{S}^{3}$FP by successfully detecting the errors of all 70 considered benchmarks while the two baselines only report errors for part of them. By taking as input the inferred ranges of Eiffel, Herbie obtains an average accuracy improvement of 3.35 bits and up to 53.3 bits.

Following Chaudhuri, Sankaranarayanan, and Vardi, we say that a function $f:[0,1] \to [0,1]$ is $r$-regular if there is a B\"{u}chi automaton that accepts precisely the set of base $r \in \mathbb{N}$ representations of elements of the graph of $f$. We show that a continuous $r$-regular function $f$ is locally affine away from a nowhere dense, Lebesgue null, subset of $[0,1]$. As a corollary we establish that every differentiable $r$-regular function is affine. It follows that checking whether an $r$-regular function is differentiable is in $\operatorname{PSPACE}$. Our proofs rely crucially on connections between automata theory and metric geometry developed by Charlier, Leroy, and Rigo.