Carlos Augusto, S Cunha, Departmento De Informática · 2008
Abstract. Current processors are based on a multithreaded architecture. Simultaneous Multithreading (SMT) techniques are used to increase instruction throughput under a multiprogramming workload; however, it does not improve performance when only a single thread is executing. This communication explores Speculative Precomputation, a technique that uses idle thread contexts in a multithreaded architecture to improve the performance of singlethreaded applications. It reduces program stalls, generated by data cache misses, using available thread contexts to prefetch these data. Speculative Precomputation tasks are described, and the examination of basic triggers and chaining triggers are made, using a Intel Itanium ISA processor as the evaluation base. 1
Cited by 0
David Corne, Alan Reynolds · 2011
We discuss the scenario of developing an optimizer for a given space of problem instances. Standard practice typically resorts to choosing a broad approach (such as evolutionary search), then tuning the optimizer based on example problem instances, and/or hybridizing with domain-specific heuristics and expert knowledge. This will lead to a capable optimizer for the task, but we argue that the delivered optimizer will dramatically under-exploit domain information. We propose a different approach, in which the optimizer may be capable of (comparatively) ultra-fast and effective performance on new instances. The essence of this approach is straightforward: in the extreme, we can solve all possible instances of interest during development, and then deliver an `optimizer' in the form of a lookup table. In practice, the approach effects a compromise, exploiting a very large base of pre-computed solutions to bootstrap the solving of new instances. We explore this idea in the simple context of seeding a simple evolutionary algorithm with solutions selected from a large pre-solved set. We find in three test domains that optimizers exploiting a large base of pre-solved instances can deliver significantly better results.
Cited by 1
Neil Immerman · 1999
Cited by 0
Ravi Ramamoorthi · now publishers, Inc. eBooks · 2007
Precomputation-Based Rendering presents a unified mathematical view of precomputation-based rendering, while discussing its motivation, history and current and future research directions. It goes back to some of the early origins of precomputation-based rendering in replaying offline solutions for image relighting. Following this, it describes the new innovations in terms of environment maps and spherical harmonic convolution that inspired the PRT method of Sloan et al. in 2002, the approach that for the first time brought precomputation-based ideas into the mainstream of real-time rendering. It goes on to discuss a number of new innovations in this field over the past six years, to all-frequency effects, changing lighting and view, reflectance editing, dynamic scenes and lighting design. Precomputation-Based Rendering is an invaluable reference for students and computer graphics researchers. It will also be of interest to professional graphics practitioners.
Cited by 15
Ravi Ramamoorthi · Foundations and Trends® in Computer Graphics and Vision · 2009
High quality image synthesis is a long-standing goal in computer graphics. Complex lighting, reflection, shadow and global illumination effects can be rendered with modern image synthesis algorithms, but those methods are focused on offline computation of a single image. They are far from interactive, and the image must be recomputed from scratch when any aspect of the scene changes. On the other hand, real-time rendering often fixes the object geometry and other attributes, such as relighting a static image for lighting design. In these cases, the final image or rendering is a linear combination of basis images or radiance distributions due to individual lights. We can therefore precompute offline solutions to each individual light or lighting basis function, combining them efficiently for real-time image synthesis. Precomputationbased relighting and radiance transfer has a long history with a spurt of renewed interest, including adoption in commercial video games, due to recent mathematical developments and hardware advances. In this survey, we describe the mathematical foundations, history, current research and future directions for precomputation-based rendering.
Cited by 54
Jamison D. Collins, Dean M. Tullsen, Hong Wang et al. · 2005
A large number of memory accesses in memory-bound applications are irregular, such as pointer dereferences, and can be effectively targeted by thread-based prefetching techniques like Speculative Precomputation. These techniques execute instructions, for example on an available SMT thread context, that have been extracted directly from the program they are trying to accelerate. Proposed techniques typically require manual user intervention to extract and optimize instruction sequences. This paper proposes Dynamic Speculative Precomputation, which performs all necessary instruction analysis, extraction, and optimization through the use of back-end instruction analysis hardware, located off the processor's critical path. For a set of memory limited benchmarks an average speedup of 14% is achieved when constructing simple p-slices, and this gain grows to 33% when making use of aggressive optimizations.
Cited by 53
Max Böhm, Ewald Speckenmeyer · Kölner Universitäts PublikationsServer (Universität zu Köln) · 1996
An algorithm, called PLB is introduced, which redistributes workload in a processor network N in order to supply every processor of N with (about) the same amount of workload. PLB is defined in its basic form for trees, but can be extended to other topologies. The redistribution is done locally on the basis of information of over- or underload in subnetworks of N. We show, that PLB performs O(d) steps, only, where d denotes the diameter of N, and in the average case at most four times as many workload has to be migrated in complete binary trees compared to clique networks, the best possible networks. We describe an implementation of PLB and present experimental results when solving the Boolean satisfiability problem, demonstrating that PLB performs very well in practice.
Cited by 0
2008
Abstract — A major algorithmic challenge posed by QoS routing is the need to promptly identify a suitable path upon a connection request, while at the same time ensure that the selected path is satisfactory, both in terms of the connection’s QoS requirements, as well as in terms of the global utilization of network resources. In many practical cases, a precomputation scheme offers a suitable solution to the problem: a background process prepares a data base, which enables to identify a suitable path upon each connection request, through a simple, fast, procedure. While much work has been done in terms of path selection algorithms, the precomputation perspective got little attention. Simplistic adaptations of standard algorithms turn to be inefficient. Accordingly, we consider the precomputation perspective, focusing on two major settings of QoS routing. The first is the (practically important) special case where the QoS constraint is of the “bottleneck ” type, e.g. a bandwidth requirement, and network optimization is sought through hop minimization. For this setting, the standard Bellman-Ford algorithm offers a straightforward precomputation scheme. However, we show that, by exploiting the typical hierarchical structure of large-scale networks, one can achieve a substantial improvement in terms of computational complexity. Then, we turn to consider the more general setting of “additive ” QoS constraints (e.g., delay) and general link costs. As the routing problem becomes NP-hard, we focus on ¢-optimal approximations, and derive a precomputation scheme that offers a major improvement over the standard approach. Keywords—QoS, Routing, Precomputation, Hierarchical networks. I.
Cited by 0
Bohan Wang, Fanjie Ji, Y. Sun et al. · IACR Transactions on Cryptographic Hardware and Embedded Systems · 2024
At Eurocrypt 2014, Duc, Dziembowski and Faust proposed the random probing model to bridge the gap between the probing model proposed at Crypto 2003 and the noisy model proposed at Eurocrypt 2013. Compared with the probing model whose noise in the leakages should (linearly) increase with the number of shares, the random probing model allows each variable leak its value with a probability p, which reflects the physical reality of side channels much better. In Crypto 2020, Belaïd et al. proposed the Random Probing Expandability (RPE) security ensuring the random probing security for arbitrary order masking algorithms with constant leakage probability. However, the complexity of existing RPE algorithms is much higher than that of the probing secure algorithms, which is short of practical usage. In this paper, we investigate the random probing security with precomputation, where a masked cryptographic implementation can be divided into two phases. The first phase, called preprocessing, takes random bits and returns a number of precomputed values. The second phase, called online computation, takes input (e.g., plaintext and shares of secret) and precomputed values to calculate output (e.g., ciphertext) efficiently. We describe a random probing secure precomputable scheme, which transforms an arbitrary circuit compiler with tolerant leakage probability p into a precomputable one by adding a public (but random) share that is calculated in the online phase and the tolerant leakage probability of the new compiler is min{p, 2−5.01}. Then, we apply the new scheme to the bitsliced AES. Notably, the implementation under ARM Cortex M architecture shows that the performance of the online phase is significantly improved and even comparable to masking schemes only secure in the probing model.
Cited by 0Open access
Eric Allender · Lecture notes in computer science · 1986
Cited by 2
Weijia Wang, Fanjie Ji, Juelin Zhang et al. · IACR Transactions on Cryptographic Hardware and Embedded Systems · 2023
At CHES 2022, Wang et al. described a new paradigm for masked implementations using private circuits, where most intermediates can be precomputed before the input shares are accessed, significantly accelerating the online execution of masked functions. However, the masking scheme they proposed mainly featured (and was designed for) the cost amortization, leaving its (limited) suitability in the above precomputation-based paradigm just as a bonus. This paper aims to provide an efficient, reliable, easy-to-use, and precomputation-compatible masking scheme. We propose a new masked multiplication over the finite field Fq suitable for the precomputation, and prove its security in the composable notion called Probing-Isolating Non-Inference (PINI). Particularly, the operations (e.g., AND and XOR) in the binary field can be achieved by assigning q = 2, allowing the bitsliced implementation that has been shown to be quite efficient for the software implementations. The new masking scheme is applied to leverage the masking of AES and SKINNY block ciphers on ARM Cortex M architecture. The performance results show that the new scheme contributes to a significant speed-up compared with the state-of-the-art implementations. For SKINNY with block size 64, the speed and RAM requirement can be significantly improved (saving around 45% cycles in the online-computation and 60% RAM space for precomputed values) from AES-128, thanks to its smaller number of AND gates. Besides the security proof by hand, we provide formal verifications for the multiplication and T-test evaluations for the masked implementations of AES and SKINNY. Because of the structure of the new masked multiplication, our formal verification can be performed for security orders up to 16.
Cited by 4Open access
이필중 · Open Access System for Information Sharing (Pohang University of Science and Technology) · 2018
Cited by 19
For Low Power, Mazhar Alidina, Srinivas Devadas et al. · 2009
Abstract We address the problem of optimizing logic-level sequential circuits for low power. We present a powerful sequential logic optimization method that is based on selectively precomputing the output logic values of the circuit one clock cycle before they are required, and using the precomputed values to reduce internal switching activity in the succeeding clock cycle. We present two different precomputation architectures which exploit this observation. The primary optimization step is the synthesis of the precomputation logic, which computes the output values for a subset of input conditions. If the output values can be precomputed, the original logic circuit can be "turned off " in the next clock cycle and will have substantially re- duced switching activity. The size of the precomputation logic determines the power dissipation reduction, area increase and delay increase relative to the original circuit. Given a logic-level sequential circuit, we present an automatic method of synthesizing pre- computation logic so as to achieve maximal reductions in power dissipation. We present exper- imental results on various sequential circuits. Upto 60 percent reductions in average switching activity and power dissipation are possible with marginal increases in circuit area and delay.
Cited by 0
Collins, Jamison, Sair, Suleyman, Calder, Brad et al. · eScholarship (California Digital Library) · 2002
Data prefetching effectively reduces the negative effects of long\nload latencies on the performance of modern processors. Hardware prefetchers\nemploy hardware structures to predict future memory addresses based on previous\npatterns. Thread-based prefetchers use portions of the actual program code to\ndetermine future load addresses for prediction. In this paper, we combine both\nof these techniques to address the memory performance of pointer-based\napplications. We combine a thread-based prefetcher, based on speculative\nprecomputation, with a pointer cache. The pointer cache is a new hardware\naddress predictor that tracks pointer transitions. Previously proposed\nthread-based prefetchers are limited in how far they can run ahead of the main\nthread in the face of recurrent dependent loads. When combined with the\npointer cache, a speculative thread can make better progress ahead of the main\nthread, rapidly traversing data structures, despite pointer transition cache\nmisses. The pointer cache allows the consumers of a pointer load miss to issue\nbefore the data actually arrives. Our results show that using a pointer cache\nwith speculative precomputation achieves a 65% speedup on average over a\nspeculative precompution architecture with a larger L3 cache.Pre-2018 CSE ID: CS2002-0712
Cited by 1
이필중 · Open Access System for Information Sharing (Pohang University of Science and Technology) · 2018
Cited by 0
Filip Malmberg, Robin Strand · Lecture notes in computer science · 2013
Cited by 1
Aniket Deshmukh, Li Cai, Yale N. Patt · 2024
Out-of-order cores rely on high-accuracy branch predictors to supply useful instructions to the processor backend. However, there remains a large fraction of mispredictions caused by hard-to-predict (H2P) branches that modern predictors have been unable to improve. Precomputation is an alternative to prediction that speculatively executes the dependence chain of a branch earlier to override the branch predictor at Fetch time. However, prior work sacrifices H2P branch coverage and precomputation accuracy to produce timely results. Our work relaxes this timeliness constraint by using precomputation results to issue early misprediction flushes instead of overriding the branch predictor. This allows us to construct a highly accurate precomputation thread with good misprediction coverage, without sacrificing timeliness. The thread is efficient as it utilizes on-core execution resources and re-uses existing hardware for issuing early flushes. Using our Timely, Efficient, and Accurate thread for precomputation yields a 10.1% improvement in performance over an aggressive baseline OoO core.
Cited by 1
Islam Atta, Xin Tong, Vijayalakshmi Srinivasan et al. · 2015
This work revisits precomputation prefetching targeting long access latency loads with access patterns that are hard to predict. It presents Ekivolos, a precomputation prefetcher system that automatically builds prefetching slices that contain enough control flow instructions to faithfully and autonomously recreate the program's access behavior without inducing monitoring and execution overhead on the main thread. Ekivolos departs from the traditional notion of creating optimized short slices. In contrast, it shows that even longer slices can run ahead of the main thread and perform useful prefetches as long as they are sufficiently accurate. Ekivolos operates on arbitrary application binaries and takes advantage of the observed execution paths in creating its slices. On a set of emerging workloads Ekivolos outperforms three state-of-the-art hardware prefetchers and previously proposed precomputation-based prefetchers.
Cited by 9
William J. Huggins, Jarrod R. McClean · Quantum · 2024
Real-world applications of computing can be extremely time-sensitive. It would be valuable if we could accelerate such tasks by performing some of the work ahead of time. Motivated by this, we propose a cost model for quantum algorithms that allows quantum precomputation; i.e., for a polynomial amount of ``free'' computation before the input to an algorithm is fully specified, and methods for taking advantage of it. We analyze two families of unitaries that are asymptotically more efficient to implement in this cost model than in the standard one. The first example of quantum precomputation, based on density matrix exponentiation, could offer an exponential advantage under certain conditions. The second example uses a variant of gate teleportation to achieve a quadratic advantage when compared with implementing the unitaries directly. These examples hint that quantum precomputation may offer a new arena in which to seek quantum advantage.
Cited by 7Open access
Chae Hoon Lim, Hyo Sun Hwang, Pil Joong Lee · 2007
Multiplication and modular reduction of long integers are two primitive operations for the implementation of most public key crypto algorithms. Multiplication can be best performed using Karatsuba's divide-and-conquer technique. However, the modular reduction process is more complicated and time-consuming. Thus an efficient implementation of modular reduction operation is one of main factors affecting the performance of public key cryptosystems. In this paper, we investigate a method for speeding up modular reduction using more or less precomputation based on the modulus, and present implementation results of various algorithms including our proposed methods. 1 Introduction There are two approaches to reducing the computation time for modular exponentiation; reducing the number of modular multiplications required and reducing the computation time for modular multiplication. Since modular exponentiation requires hundreds of modular multiplications, a small improvement by the latter app...
Cited by 0