home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #16 / NN_1992_16.iso / spool / comp / arch / 8226 < prev    next >
Encoding:
Internet Message Format  |  1992-07-23  |  2.8 KB
  1. Path: sparky!uunet!pmafire!news.dell.com!swrinde!mips!news.cs.indiana.edu!umn.edu!orstnews!pmontgom
  2. From: pmontgom@math.orst.edu (Peter Montgomery)
  3. Newsgroups: comp.arch
  4. Subject: Re: Running Sum Adders
  5. Message-ID: <1992Jul23.154921.23631@talon.ucs.orst.edu>
  6. Date: 23 Jul 92 15:49:21 GMT
  7. References: <1992Jul21.194623.26688@jarvis.csri.toronto.edu> <MISHA.92Jul22214158@espresso.ai.mit.edu>
  8. Sender: usenet@talon.ucs.orst.edu (Usenet News admin)
  9. Organization: Oregon State University Math Department
  10. Lines: 50
  11. Nntp-Posting-Host: lab2.math.orst.edu
  12.  
  13. In article <MISHA.92Jul22214158@espresso.ai.mit.edu>
  14. misha@ai.mit.edu (Mike Bolotski) writes:
  15. >>>> On 21 Jul 92 23:46:23 GMT, ronus@eecg.toronto.edu (Ron White) said:
  16.  
  17. >Ron> Hi.  I have a paper that mentions the use of a: "running sum
  18. >Ron> adder commonly found parallel processing units".  The paper
  19. >Ron> doesn't go into any more detail and doesn't list any references
  20. >Ron> w.r.t. this type of parallel adder.  Could someone point me to a
  21. >Ron> reference that will explain the operation of a "running sum
  22. >Ron> adder" ?
  23.  
  24. >I'll bet they're referring to a carry-save adder.  You can look
  25. >that up in any text on computer arithmetic.
  26.  
  27.         Also look up ``fetch-and-add'' instruction, FAD.  This
  28. takes and address addr and an (integer) increment amt.
  29.  
  30.         FAD  addr,amt   replaces  (addr) <- (addr) + amt
  31.  
  32. which returning the old contents (addr).
  33.  
  34.         The application to parallelism comes because several
  35. processors might increment the same address at once.  Consider
  36.  
  37.         Processor 0:  FAD  addr0,amt0
  38.         Processor 1:  FAD  addr0,amt1
  39.         Processor 2:  FAD  addr2,amt2
  40.         Processor 3:  FAD  addr0,amt3
  41.  
  42. where addr0 <> addr2.  There are many acceptable behaviors.
  43. All increment (addr0) by amt0 + amt1 + amt3 and (addr2) by amt2,
  44. while returning the old (addr2) to Processor 2.
  45. The order of the three increments on addr0 is not specified, but each
  46. is treated as an atomic operation.  For example, it might
  47. return the old (addr0) to Processor 1, (addr0) + amt1 to
  48. Processor 3, and (addr0) + amt1 + amt3 to Processor 0.
  49.  
  50.         The special aspect of this instruction is that memory
  51. interface boxes can detect the duplicate addr0 and combine the
  52. requests to reduce congestion.  For example, if it observes that
  53. Processors 0 and 1 are incrementing the same address, it can
  54. merge the two transactions into a single increment by amt0 + amt1.
  55. Then, when the old (addr) comes back, the box can send this
  56. (addr0) to Processor 0 and (addr0) + amt0 to Processor 1.
  57. The corresponding box for Processors 2 and 3 would see different
  58. addresses and need to make two separate memory operations.
  59. -- 
  60. New address as of June 26, 1992:
  61.         Peter L. Montgomery              Internet: pmontgom@math.orst.edu
  62.         Dept. of Mathematics, Oregon State Univ, Corvallis, OR 97331-4605 USA
  63.