attachment:notes_bradshaw.txt of msri07/notes

   1 1:30 p.m.
   2 Loosely Dependent Parallel Processes
   3 
   4 Can be seen as a continuation of the DSAGE talk.
   5 
   6 Two opposite ends of the spectrum:  Massively Parallel or Task Farm.
   7 
   8 Massively Parallel:  MPI/shared memory, Master and slaves, constant communication
   9 Task Farm:  Occasional network access, controller and workers, intermittent communication
  10 
  11 Integer Factorization:
  12 	Trial Division (small primes)
  13 	Quadratic Sieve ("reasonably" sized primes)
  14 	Elliptic curve methods (probabilistic, dominated by size of smallest factor)
  15 All of these methods are embarassingly (proudly) parallelizable.
  16 
  17 DSAGE implementation:
  18 	1 worker does Qsieve, others do ECM.  If an ECM worker factors the number, the sieve is killed and restarted with a nonprime factor.  The ECMs work on factoring the factors as well.
  19   Trial division fits in as a quick check at the beginning.
  20 
  21 
  22 The workers are SAGE instances, themselves, and have DSAGE.  One can be a Worker/Controller so you can save a controller, go offline, come back, and see the results.
  23 
  24 Communication Bottleneck
  25 	All communicatoin passes through server and client
  26 	Current implementation is extremely course-grained (workers only listen for kill signals)
  27 
  28 Worker-to-Worker
  29 Pros:
  30 	Can open up a wider range of problems, such as periodically sharing boundary data
  31 Cons:
  32 	Firewalls, etc.
  33 
  34 Inter-process communication can be done in DSAGE, but it needs more work.