English subtitles

← Chaining Is Bad - Intro to Parallel Programming

Get Embed Code
2 Languages

Showing Revision 5 created 05/24/2016 by Udacity Robot.

  1. So let's think about how chaining would behave in a parallel setting.
  2. For construction, that means we have many items to put into the hash table, 1 per thread.
  3. Per look up, that means we have many keys to look up in the hash table; again, 1 per thread.
  4. And chaining has 2 main disadvantages.
  5. Number 1, let's say we're looking up many items, 1 per thread,
  6. and we know to look up 1 item,
  7. we calculate the hash function for that item.
  8. That paralyzes nicely. It's just a map operation.
  9. More problematic, however, is searching the link list in the bucket.
  10. So we have a number of threads here.
  11. Each thread ends up looking in a different bucket.
  12. This particular bucket has 3 items.
  13. The bucket for thread 2 has 2 items,
  14. but the bucket for thread 1 has many, many, many items.
  15. Some threads, like thread 2, might find their item right away.
  16. Some threads, like thread 1, for instance,
  17. might have to visit many or even all the items in a lengthy link list before finding its item.
  18. Because threads within a warp run in lock step,
  19. the run time of a warp is completely dependent on the slowest lookup within the warp.
  20. The other threads in the warp have to wait until the slowest item is found,
  21. and this behavior, as you might imagine, is bad.