home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #26 / NN_1992_26.iso / spool / comp / arch / 10475 < prev    next >
Encoding:
Text File  |  1992-11-08  |  1.3 KB  |  30 lines
  1. Newsgroups: comp.arch
  2. Path: sparky!uunet!ukma!wupost!crcnis1.unl.edu!moe.ksu.ksu.edu!hobbes.physics.uiowa.edu!news.uiowa.edu!news
  3. From: jones@pyrite.cs.uiowa.edu (Douglas W. Jones,201H MLH,3193350740,3193382879)
  4. Subject: Re: hardware sorting
  5. Sender: news@news.uiowa.edu (News)
  6. Message-ID: <1992Nov6.202127.28890@news.uiowa.edu>
  7. Date: Fri, 6 Nov 1992 20:21:27 GMT
  8. References: <1992Nov6.165252.21619@infodev.cam.ac.uk>
  9. Nntp-Posting-Host: pyrite.cs.uiowa.edu
  10. Organization: University of Iowa, Iowa City, IA, USA
  11. Lines: 17
  12.  
  13. From article <1992Nov6.165252.21619@infodev.cam.ac.uk>, by swm11@cl.cam.ac.uk (Simon Moore):
  14. > 
  15. > I have a requirement for a hardware sorter to sort
  16. > deadlines for high speed real-time earliest deadline
  17. > first scheduling.  New deadlines can arrive at a peak
  18. > rate of one every cycle and the earliest deadline
  19. > needs to be extracted every 8 cycles.
  20.  
  21. You don't want a hardware sorter, you want a hardware priority queue, aka
  22. heap manager.  Yes, work has been done on this.  For example, Quinn and
  23. Deo have surveyed some early work on this in their Sept 1984 paper in
  24. Computing Surveys.  Since then, other work has been done on priority queues
  25. (by me, for example), but mostly focusing on high speed software
  26. implementations.  I don't know if anyone has translated the best of these
  27. results to useful hardware.
  28.                 Doug Jones
  29.                 jones@cs.uiowa.edu
  30.