Arithmetic data value speculation.

Arithmetic approximation is used to decrease the latency of an arithmetic circuit by shortening the critical path delay or the sampling period so that result is not guaranteed to be correct for every input combination.Thus, an acceptable compromise between the circuit latency and the average probability of correctness drives the circuit design. Two methods of arithmetic approximation are: temporally incompleteness where circuits quote the result before the critical path delay (overclocking); and logically incompleteness where circuits use simplified logic, so that most input cases are calculated correctly, but the slowest cases are calculated incorrectly. Arithmetic data value speculation (ADVS) is a speculation scheme based on arithmetic approximation, and is used to increase the throughput of a general purpose processor. ADVS is similar to branch prediction, an arithmetic instruction is issued to an exact arithmetic unit and an approximate arithmetic unit which provides an approximate result faster than the exact counterpart. The approximate result is forwarded to dependent operations so they may be speculatively issued. When the exact result is eventually known, it is compared to the approximate result, and the pipeline is flushed if they differ. This thesis, "ArithmeticDataValue Speculation", presents work in the field of digital arithmetic and computer architecture. A summary of current probabilistic arithmetic methods from the literature is provided, and novel designs of approximate integer arithmetic units are presented, including results from logical synthesis. A case study demonstrates approximate arithmetic units used to increase the average throughput of benchmark programs by speculatively issuing dependent operations in a RISC processor. The average correctness of the approximate arithmetic units are shown to be highly data dependent, results vary depending on the benchmarks being run. In addition, the average correctness when running benchmarks is consistently higher than for random inputs. Simulations show that many arithmetic operations are often repeated in the same benchmark, leading to a high variation in correctness. Speculative gains from one operation can be offset by speculation losses due repeated incorrect approximation of another approximate unit, so typical throughput gains through speculation in a general purpose processor pipeline are low. The minimum threshold correctness of an approximate arithmetic unit used for speculation is shown to be approximately 95%. Logic synthesis is used to determine power, area and timing information for approximate units implemented from novel algorithms, and show a reduction in arithmetic cycle latency for integer operations, and the expense of 50% leakage and area, and 90% dynamic power. Value speculation can be complemented by result caching; repeated pipeline flushes can be avoided if the correct result is know before speculation, the average operation latency can be reduced, and caching can be used for operations that are difficult to approximate.

Author dc:creator

• Kelly, Daniel R.

Advisors dc:contributor.advisor

• Phillips, Braden Jace
• Al-Sarawi, Said Fares Khalil

• arithmetic; speculation; estimation; value-prediction; computer architecture; hardware; throughput; probabalistic computing; multiplication; division; parity check decoder; LDPC; signal processing

Handle dc:identifier.uri

http://hdl.handle.net/2440/70234

OAI identifier oai:identifier

oai:digital.library.adelaide.edu.au:2440/70234