Path: utzoo!attcan!uunet!abvax!icd.ab.com!ejp From: ejp@icd.ab.com (Ed Prochak) Newsgroups: comp.software-eng Subject: Re: Tolerance Message-ID: <2053@abvax.UUCP> Date: 12 Feb 91 15:18:35 GMT References: <1401@ucl-cs.uucp> <27A9B451.48BF@tct.uucp> <15863.27ad36b6@levels.sait.edu.au> <777@caslon.cs.arizona.edu> <87999@tut.cis.ohio-state.edu> <5614@skye.cs.ed.ac.uk> <665834913.1874@minster.york.ac.uk> Sender: news@abvax.UUCP Reply-To: ejp@icd.ab.com (Ed Prochak) Organization: Allen-Bradley Company; Industrial Computer & Communications Group Lines: 150 In article <665834913.1874@minster.york.ac.uk>, mrp@minster.york.ac.uk writes: |> The point being missed so far is when can a system 'make-do' with an |> 'imprecise/less-accurate/less tolerant/in-exact/imprefect' result. |> |> The driving force behind a system using imprecision is the |> time-precision trade off. This requires that algorithms are written |> so the preciseness of the result as it is sampled during the execution |> of the task rises as more time is spent executing the task. Thus when |> the task stops the precision of the result is dependent on how much of |> the code the task managed to execute. [see Lin,Swaminathan & Liu, |> IEEE RTS Symposium 1987]. I think that the real point being missed is that the tolerance has nothing to do with the result, be it numerical, alphabetic, or other. |> [deleted description of time critical numerical problem & solution] |> |> - Martin |> |> #===============================#===========================================# |> | Martin Portman | Phone: (0904) 432735 | |> | Dept. of Comp. Science | JANET: mrp@uk.ac.york.minster | |> | University of York | UUCP: ...!mcsun!ukc!minster!mrp | |> | Heslington | ARPA: | |> | YORK YO1 5DD ENGLAND | mrp%minster.york.ac.uk@nsfnet-relay.ac.uk | |> #===============================#===========================================# In article <785@caslon.cs.arizona.edu>, dave@cs.arizona.edu (Dave P. Schaumann) writes: >In article <777@caslon.cs.arizona.edu> I wrote: >> Numerical analysis aside, I can't imagine a single instance of >> "close is good enough". > >khb@chiba.Eng.Sun.COM (Keith Bierman fpgroup) wrote: >>Most code optimizations, to wit: >> register allocation (must be correct, but need not be optimal) >> instruction scheduling (ditto) >> etc. >>and >> traveling salesfolk (ditto) >> chess/games in general programs (ditto) >> etc. > >cwk@ORCRIST.GANDALF.CS.CMU.EDU (Charles Krueger) wrote: >>How about weather predictions? [Mentions other simulations] >> >>What goes on inside the computer, however, is still as precise as ever. > >djbailey@skyler.mavd.honeywell.com wrote >>[...] >>"Tolerance" is appropriate to higher level system requirements. If >>you could quantify the tolerance in requirements, you could have a >>very significant impact on how software development contracts are >>written and probably reduce a lot of arguments. an excellant observation IMHO > >Ok, so I stand corrected. There are a lot of applications out there that >don't need exact answers. But my question was in the context of code re-use. >How could you say something like, "well, I really need a stack, but I'll >settle for something sort of stacky"? Will we see code like this in the >future: > > assert( stackyness(re_used_type) > 0.9 ) ; /* stackyness(a real stack)=1.0 */ I don't think so, because this is not where the tolerance lies. > >I can't see how the "tolerence paradigm" could possibly lead to a reasonable >means of code re-use. > >Dave Schaumann | And then -- what then? Then, future... >dave@cs.arizona.edu | -Weather Report Saying software has a tolerance on the output produced misses the point of tolerances completely. Some folks are on the right track, but I still haven't seen a clearcut example. Since Dave provided the question, I will use his stack as an example. The "tolerence(sic) paradigm" doesn't require that the operations not be performed precisely, but that certain other parameters may vary greatly according to the implementation. Now a stack is a stack is a stack. All things that claim to be stacks must be stacks 100%. There must be at least three fundamental operations: Initialize, Push, and Pop. the tolerance comes in when you try to compare two implementations of stacks. Consider first a stack implemented using a fixed size array. All three operations in this case are fast. But there is a finite limit to how much can be pushed onto the stack before the array is filled. The specifications might provide the info. that push/pop uses Xmicroseconds and there is a fixed memory cost of Ykilobytes (even when the stack is empty that array is there.) This stack has very tight timing and memory tolerances, but at the cost of always having more memory for the stack than you need. Now a second implementation uses linked list, with elements allocated as needed. Maybe the Push and Pop operations are slower in this case, say 2Xmicroseconds. but the memory constraint is removed. The stack size limit is essentially infinite, or at least as big as the disc swap space on a virtual memory system. And actually, the timing of the Push and Pop operations have more variation as the OS might possibly do swaps during the calls. The stack example is very trivial, but the point is that tolerance applies to more than just the operation being performed. It is an object view of the software, you don't look at the internals, how it is implemented. You think, "I need something to do these operations with this transaction rate." Want a real life example? Consider a printer. it must locate the characters and image them at the correct point size. there is little or no tolerance there, but how fast the pages come out has a good deal of tolerance. A customer expects simple pages to come out faster than more complex pages. there are two measurements that may vary: print speed and page complexity. Print speed is relatively easy to define and can be measured precisely. Complexity of the text is not so easily defined and may have a wide tolerance in the customer's view. In summary: the software has properties that can be measured. The measurements are sometimes imprecise, & othertimes, are allowed to vary because that property is less important. The software must still provide correct results! As a final example, consider the tolerance in the hardware world. What property of a memory IC has tolerances associated with it? Certainly the memory cell must return the exact value placed there by the last write operation (zero tolerance here). The IC is sold on the properties of how fast and how many, and the greatest tolerance is on the speed. Edward J. Prochak Voice: w(216)646-4663 h(216)349-1821 Email: {cwjcc,pyramid,decvax,uunet}!ejp@icd.ab.com USmail: Allen-Bradley, 747 Alpha Drive, Highland Heights,OH 44143 Wellington: ENGINEERING is "the ability to do for one dollar, what any damn fool can do for two."