David Gregg

Integer division and remainder are relatively complicated, expensive operations. Most modern processors have at least one integer multiplier unit that has both low latency (typically between 3 and 5 cycles) and high throughput (typically the unit can complete a multiply operation every cycle). In contrast, most modern processors do not have a fast integer division … Read more

Almost all modern processors provide special-purpose instructions for integer multiplication. However, some applications require integer values that are larger than fit in a single machine word, such as 256 bit integers. We can multiply these big integer values using a sequence of smaller multiplies. For example, multiplying two 256-bit integer values might be completed with … Read more

In some applications, such as many cryptography algorithms, multiplication by a known integer constant is a common operation. It’s well known that integer multiplication with a constant can be computed with a sequence of shifts and adds. Most modern processors already have fast integer multiplication units, so in software it is usually faster to use … Read more

Matrix multiplication is one of the commonly-used computations across a wide range of applications. For example, most implementations of neural networks implement very large numbers of matrix multiplications. Almost all processor and GPU manufacturers provide libraries with carefully hand-tuned fast matrix multiplication routines. All the best-known algorithms matrix multiplication are out-of-place; that is, the result … Read more

[Note: this is quite a difficult project. To take the project, you should already have experience with OpenMP, or have an interest in parallel computing, or just be a very good programmer.] OpenMP is a small domain-specific language for describing parallelism in C, C++ and Fortran programs. OpenMP was originally designed to express parallelism using … Read more

Matrix multiplication is one of the commonly-used computations across a wide range of applications. For example, most implementations of neural networks implement very large numbers of matrix multiplications. Almost all processor and GPU manufacturers provide libraries with carefully hand-tuned fast matrix multiplication routines. All the best-known algorithms matrix multiplication are out-of-place; that is, the result … Read more

Many cryptographic schemes rely on modular arithmetic. Modular arithmetic is a system of arithmetic operators on integers where the numbers “wrap around” back to zero when they reach a value called the modulus. For example, if our modulus is 17, then (12 + 14) mod 17 = 9. When we implement modular arithmetic, a key … Read more

A sparse matrix is a two-dimensional array where most of the elements are zero. If a very large sparse matrix is stored in normal array format, a huge amount of memory will be needed to store values that are almost all zero. Instead, large sparse matrices are normally stored in a compacted form, where only … Read more

Modular arithmetic is commonly used in cryptographic schemes such as elliptic curve cryptography. A modular number system can represent whole numbers in the range 0 up to some value p-1, where p is the modulus. Modular number systems wrap around. For example, if the modulus is 7, then (4 + 6) mod 7 = 10 … Read more

ABC is an open-source logic synthesis and optimization tool developed by Alan Mishchenko at the University of California at Berkeley. ABC specializes in optimizing digital logic circuits at the circuit level, and some commercial hardware synthesis tools incorporate ABC as part of their design flow to improve their circuit optimization. ABC is a large logic … Read more