Eric Postpischil's Work Samples

Work Samples

Apple, Inc.

These are single-precision trigonometric functions I designed and implemented in hand-coded assembly. They are fast, deliver faithfully rounded results, and conform to standards. I used Maple to design the approximating polynomials and other mathematics.

Argument reduction in the sine, cosine, and tangent routines is interesting. Because π is irrational, some very large floating-point numbers are very close to multiples of π/2. These numbers have very small sines or cosines. Determining the correct result requires finding a remainder that is many orders of magnitude smaller than the least significant bit in the input.

In order to produce a faithfully rounded result, the error in the remainder operation, the error in the polynomial, and the rounding errors in the polynomial evaluation must be, in total, less than the value of the least significant bit of the result expressed in single-precision.

A faithfully rounded result is one of the two floating-point numbers bracketing the exact mathematical answer. This criterion is used because determining the nearest floating-point number requires excessive time when the exact answer is very near the point midway between two floating-point numbers.

I tested each single-argument routine with each of the 4,294,967,296 input values.

The times shown are CPU cycles on an Intel Core 2, measured as the duration per call when called repeatedly. (This represents throughput. The latency, the duration from start of a call to when the result is available, is longer.) For comparison, times measured for Intel's Integrated Performance Primitives (IPP) are shown. A routine has several times because its behavior varies over its domain. These times are for normal numbers, not infinities, denormals, NaNs, or out-of-domain values.

The sine and cosine routines spike to 75 and 78 cycles for a small part of their input domains (four exponent values out of 254) because the table entries share address bits with a stack location, causing the processor to delay execution until it determines there is no actual physical address collision.

The sine, cosine, and tangent routines use generated data in sinfcosfTable.s and tanfTable.s, but the generating code is not publicly available. (It is straightforward arithmetic but was not published by Apple.)

Construction of a High-Performance FFT

Construction of a High-Performance FFT (PDF). (Also available as Microsoft Word in a ZIP file.)

The design is discussed almost entirely in C but divides the work into subroutines that can clearly be implemented as high-performance code on an ordinary processor or on a single-instruction multiple-data processor. (That is, the routines perform parallel calculations on separate data, so it is clear that multiple instructions can be issued separately.)

You are welcome to copy the paper for the purpose of reviewing my work. If you would like to use the paper in your work, please read the license in the ZIP file.

Assembly Language Code Sample

A radix-4 FFT butterfly subroutine (text file).

First, if you have seen an FFT implementation before, search for the first occurrence of "1:". This is a label which starts the main loop. In some FFT implementations, the butterfly calculations are a mess. I sought to express the calculations cleanly and bring out the symmetry in the mathematics.

Second, if you have some experience with high-performance code or instruction scheduling, search for the second occurrence of "1:". Here begins a loop that performs the same calculations, but the instructions are reordered for high performance. (I apologize that the documentation for this reordering is in another file that I do not have permission to publish.) This loop runs in 31 CPU cycles per iteration.

(There are two versions of the loop because the first performs the calculations in a simple serial, comprehensible manner. It works and is used for development and illustration and is not assembled in the production code.)

Zero-Knowledge Proofs, Slides From a Talk

Zero-Knowledge Proofs (PDF).

This was not prepared as a work project, but it shows some of my exposition style even though it does not include the narration that adds to the slides.

© Copyright 2003 by Eric Postpischil.