ProcessorsWantingBlocks

System for Communicating Which Processors want Which Blocks

=== Current Design===

for block in blocks:
   bool needed=GetNeededHere()
   bool read=GetReadHere()
   neededwhere = Gather(needed)
   if read :
      read(block)
      for target in neededwhere:
         send(block,to = targets)
   if needed:
      receive(block)

This performs as O(blocks * (find_out_needed + (latency+bool_send_time) * gather_time(cores) + read_time*file_contention_fn(reading_cores) + latency+ block_send_time), roughly as O(blocks * latency)

Note this is independent of the number of reading cores -- the gather serialises the load, even for multiple reading cores.

Proposed Design 1:

myneeds={}

for block in blocks:
   myneeds{block}=GetNeededHere()

whichblockswhere=Gather(myneeds)

for block in blocks
   sendblockwhere[block]=find(whichblockswhere.transpose()[block])

for block in blocks:
   bool read=GetReadHere()
   if read :
      read(block)
   for target in sendblockwhere[block]
      send(block,to = target)
   if myneeds[block]:
      receive(block)

Expected to perform as O(blocksfind_out_needed + (latency+needed_send_time) gather_time(cores) + (blocks/reading_cores)(read_timefile_contention_fn(reading_cores) + latency+ block_send_time)

Proposed Design 2:

myneeds=[{}]*len(readingcores)

for block in blocks:
   bool needed=GetNeededHere()
   for readingcore in readingcores:
      myneeds[readingcore]{block}=needed

for readingcore in readingcores:
   whichblockswhere=Gather(myneeds[readingcore])

for block in blocks
   sendblockwhere[block]=find(whichblockswhere.transpose()[block])

for block in blocks:
   bool read=GetReadHere()
   if read :
      read(block)
   for target in sendblockwhere[block]
      send(block,to = target)
   if myneeds[block]:
      receive(block)

Expected to perform as O(blocksfind_out_needed + readingcores(latency+needed_send_time/reading_cores) gather_time(cores) + (blocks/reading_cores)(read_timefile_contention_fn(reading_cores) + latency+ block_send_time)

Proposed Design 3:

myneeds=[{}]*len(readingcores)

for block in blocks:
   bool needed=GetNeededHere()
   for readingcore in readingcores:
      if needed:
          myneeds[readingcore].push_back(block)

for readingcore in readingcores:
   for source in cores
       receive(whichblockswhere[source])

for block in blocks
   for target in cores:
       if block in whichblockswhere[target]:
            sendblockwhere[block].push_back(target)

for block in blocks:
   bool read=GetReadHere()
   if read :
      read(block)
   for target in sendblockwhere[block]
      send(block,to = target)
   if myneeds[block]:
      receive(block)