home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1993 #3 / NN_1993_3.iso / spool / comp / arch / 12429 < prev    next >
Encoding:
Text File  |  1993-01-28  |  2.5 KB  |  63 lines
  1. Newsgroups: comp.arch
  2. Path: sparky!uunet!charon.amdahl.com!amdahl!rtech!sgiblab!spool.mu.edu!uwm.edu!rpi!utcsri!geac!itcyyz!yrloc!rbe
  3. From: rbe@yrloc.ipsa.reuter.COM (Robert Bernecky)
  4. Subject: Re: Control TO Data Dependence
  5. Message-ID: <1993Jan27.153136.11639@yrloc.ipsa.reuter.COM>
  6. Keywords: Control Dependence, Data Dependence, High-Level Synthesis
  7. Reply-To: rbe@yrloc.ipsa.reuter.COM (Robert Bernecky)
  8. Organization: I P Sharp Associates, Toronto
  9. References: <1993Jan23.003531.21573@cs.brown.edu>
  10. Distribution: Snake Island Research Inc
  11. Date: Wed, 27 Jan 93 15:31:36 GMT
  12. Lines: 49
  13.  
  14. In article <1993Jan23.003531.21573@cs.brown.edu> lka@lems17lems.brown.edu (Lalit K. Agarwal) writes:
  15. >Has anyone played with converting CONTROL-DEPENDENCE to DATA-DEPENDENCE in
  16. >High-Level-Synthesis or come across any algorithm for doing it in the literature.?
  17. >All suggestions are highly welcome.
  18.  
  19. This is common in APL and J. Both languages are array-oriented:
  20.     1 2 3 + 8 4 2
  21. 9 6 5
  22.  
  23. so all primitives are defined on entire arrays, rather than on scalars.
  24. Given this, programs are shorter, cleaner, more elegant, and more likely to
  25. work if you describe algorithms in terms of array operations instead of loops.
  26. Thus, you'll see expressions like this:
  27.  
  28.     X + 55* (X<4)     NB. Add 55 to those elements of X which are less than 4.
  29.  
  30. This involves knowledge of simple arithmetic identities, but there are
  31. merge and selection capabilities which permit fancier stuff:
  32.     t =. "this is my   text string'
  33.     b =. t=' '
  34.     b
  35. 0 0 0 0 1 0 0 1 0 0 1 1 1 0 0 0 0 1 0 0 0 0 0 0  
  36.     NB. The above locates blanks in t.
  37.     NB. Now replaces blanks by '*'.
  38.     t[b/i. #b] =. '*'   NB. This is part APL, part J... 
  39.     NB. #b is the shape of b, i.e., 24 
  40.     NB. i. #b is the first #b integers.
  41.     NB. b/i.#b removes from the list of #b integers those which are
  42.         not corresponding to blanks.
  43.     NB. t[...] =. '*' replaces the non-blank elements.   
  44.  
  45. This stuff is common in APL. Go read ACM SIGAPL Quote Quad conference 
  46. proceedings for more examples, or come to APL93 in Toronto this August
  47. 15-19!
  48. {I'm the Tutorials Chair...}
  49.  
  50. One last example: A model of a loom is 2.5 pages of BASIC (SEE P. Heiser,
  51. August 1981 or so BYTE article {from memory}). This compresses into
  52. about 12 characters of APL: Two indexing operations and one inner product.
  53. It also runs bags faster than BASIC. Even on one processor... 8^}
  54.  
  55. Bob
  56.  
  57.  
  58. Robert Bernecky      rbe@yrloc.ipsa.reuter.com  bernecky@itrchq.itrc.on.ca 
  59. Snake Island Research Inc  (416) 368-6944   FAX: (416) 360-4694 
  60. 18 Fifth Street, Ward's Island
  61. Toronto, Ontario M5J 2B9 
  62. Canada
  63.