CS341 Advanced Topics in Algorithms: Forum BSP Computers

2 posts 2 followers RSS feed

1. Oliver Nicholls

   #1 14:30, Mon 6 Feb 2017

   Hi Alex,

   I was hoping that you could explain more about the properties of the processors used in BSP computers, for example:

   • What kind of data can be stored in the processors' internal memory?
   • What operations can be completed in a given processor? (e.g. is it just simple operations like comparisons, or can it be even as complicated as sorting (or harder)?)
   • How much data can be contained in each input/output of a processor? (e.g. a single number? An array? A complex data structure?)

   And as a general question (with relevance to the assignment), how should one go about constructing a BSP algorithm formally? Can you point me towards any resources which solve a BSP problem? I know the slides have content covering things like broadcasting and combining, but I'm struggling to apply the examples to some of the assignment questions, and an example would greatly help. I've found plenty of papers with examples but none are suitably simple to provide clarity.

   Many thanks,

   Oliver

   0 likes
    
2. Alexander Tiskin

   #2 19:33, Wed 8 Feb 2017

   As discussed in the lectures, one can think of a BSP processor as a normal general-purpose computer that can perform any standard operations (arithmetic, Boolean, array indexing, branching) on standard data (integer, floating-point, Boolean). The technical terminology for this processor model is "von Neumann computer" in Valiant's original paper and in Bisseling's book, and "RAM" in most algorithms/complexity books. Once we connect a bunch of such processors together by a communication environment with parameters "g, l", we obtain a BSP computer.

   Attached is a description of a BSP algorithm, answering a question from the 2016 exam paper. This question was discussed in the last seminar with the non-DM group.

   1 attachment

   • PDF document temp.pdf
     89 KB
   0 likes