What did Pete Stewart think he knew about efficient implementation of floating point denormals?

Question

The most controversial part of the IEEE 754 floating-point standard is gradual denormals. Typically they trap to software rather than being implemented in hardware. In the common case where a workload has numbers that decline to zero, when they hit the denormal range, there is an abrupt slowdown of a couple of orders of magnitude until the programmer finds out what's going on and how to turn off denormals. There is a good reason for this: in a nutshell, to make them run fast, would require spending more hardware resources all the time so that, for a given budget of transistors and power, everything would run slower in throughput, latency or both: https://stackoverflow.com/questions/54937154/why-are-denormal-floating-point-values-slower-to-handle

When the IEEE 754 committee was debating the matter, DEC hired an expert numerical analyst named Pete Stewart to study it and give his opinion, expecting him to support their position (based on experience with the VAX) that denormals should not be in the standard; they were unpleasantly surprised when he claimed they could in fact be implemented efficiently: https://people.eecs.berkeley.edu/~wkahan/19July10.pdf

But I haven't been able to find any specifics on how he expected this to be done. Presumably if the method he was thinking of would really work with no downside, modern CPUs would use it.

So what was he thinking? Why doesn't it work with no downside? Why did he believe it would? Was he ignoring latency and power consumption? Was he ignoring diffuse cost? (Sure, you can make denormals just as fast as normals – by making everything slower.) Was he working on assumptions that were true only with the technology of the time? (Gate delays exceeding wire delays, floating point implemented in microcode?) Or something else I haven't thought of?

Answer 1

As far as I am familiar with the genesis of the IEEE-754 floating-point standard from the literature, G. W. Stewart never looked at implementation cost for the support of gradual underflow. He was tasked with examining its claimed advantages to floating-point computation from a numerical analysis viewpoint.

Charles Severance, "IEEE 754: An Interview with William Kahan." Computer, Vol. 31, No. 3, March 1998, pp. 114-115

Yes, DEC had been struggling to persuade us that gradual underflow was a bad thing. If they could prove it was unnecessary, there was no reason not to use DEC’s exponent bias. The exceptional handling and other details could be done with small tweaks. DEC finally commissioned one of the most prominent error analysts in the east, G.W. (Pete) Stewart, to perform the study. He was to look into the error analysis aspects to demonstrate that gradual underflow was not all that I had cracked it up to be. [...] At a meeting in Boston in 1981, Stewart reported that, on balance, he thought gradual underflow was the right thing to do. The DEC folk who had commissioned the report were rather disappointed and they said, "OK, we’ll publish this later."

Severance's interview notes entitled "An Interview with the Old Man of Floating-Point" also describe DEC's objections from a hardware implementation viewpoint (in this quote, K-C-S refers to the proposal by Kahan, Coonen, and Stone which eventually became the basis for IEEE-754):

At an early meeting of p754 in the late 1970s a hardware engineer from DEC had stated flatly that K-C-S could not be built to run as fast as VAX arithmetic hardware. Meanwhile George Taylor, then a graduate student supervised by Computer Science Prof. Dave Patterson at U.C. Berkeley, had been building K-C-S floating-point onto two accelerator boards for a VAX there. The plan was to substitute these for DEC's without changing the VAX instruction set, and then see how well software ran on each arithmetic. After Taylor showed his design to a p754 meeting nobody could dispute the feasibility of fast K-C-S floating-point.

DEC's objections to a supposedly unacceptably high implementation burden for the proposed floating-point standard were refuted by two researchers from UC Berkeley, who built standard-compliant replacements for the five VAX FPA (floating-point accelerator) boards:

George S. Taylor and David Patterson, "VAX hardware for the proposed IEEE floating-point standard." In: 5th IEEE Symposium on Computer Arithmetic, May 1981, pp. 190-196

In the summary line of table 1 in the paper one sees that the total IC count increased from 700 in DEC's original hardware to 870 for the standard compliant replacement. This 25% increase in hardware expenditure was necessary not just to support gradual underflow but all proposed new features including extended precision and square root capability. The table shows an increase from 35 to 45 ICs for normalization functionality. Table 2 shows that the execution time of the standard-compliant operations provided by the replacement boards is roughly in line with DEC's original FPA, some are a bit slower, others are a bit faster.

Answer 2

Suppose one is considering adding something to the specifications of a car that will, on 1% of units manufactured, extend the time required to perform some fabrication step by ten seconds. How much should that be expected to affect the cost of a car?

If cars are being assembled individually, the extra cost would be trivial. An average of 0.1 seconds per car. If cars are being mass-produced on an assembly line, however, the extra cost could be huge. If each station on the assembly line takes 2.5 minutes, and the extra 10 seconds of labor would have to be added at a stage that already takes 2.45 minutes, it would be necessary to either feed every car through an extra assembly line stage, or else extend the time for all assembly-line stages by 7 seconds every time a car required that extra step.

When floating-point standards were being written, floating-point operations would involve performing multiple steps performed sequentially on one number at a time. Mandated support for features like denormals would sometimes necessitate an extra step, but that would only affect the execution time for a few operations, and only by a little bit.

Modern CPUs, however, have multiple floating-point units, each of which will be pipelined so that as soon as one section finishes the first step of a floating-point operation on a number, it can start performing the first step of a floating-point operation on another number while a different section performs the second step on the first number. To make operations flow together efficiently, a scheduling unit will need to be able to predict when the results from each operation will become available.

Even if each floating-point operation would require four steps, and the time required to handle a denormalized value would be 10% of the time required to perform one step, handling such values would require either reducing the speed of all floating-point computations by 10%, making floating-point operations take five steps instead of four, or generating a pipeline stall whenever a denormalized number is processed, which would impact not only the particular computation involving the denormalized value, but could delay many other computations on multiple computation units. If computation units #2 and #3 expect that a certain result will be available from unit #1 at a certain time, but it ends up being late, units #2 and #3 will end up sitting idle for a cycle while they await the result, which will in turn cause any results that are affected by them to end up being late as well.

While the marginal cost of supporting denormalized values would have been small when using floating-point hardware that processes one number at a time, they have huge impacts on the performance of heavily pipelined multi-processors.