HOME       UP       PREV       NEXT (Classical High-Level Synthesis Continued)  

Classical High-Level Synthesis Example: Kiwi compilation of Sieve of Eratosthenes.

class primesya
{
  static int limit = 1  * 1000;
  static bool [] PA = new bool[limit];

  // This input port, vol, was added to make some input data volatile.
  [Kiwi.OutputWordPort(31, 0)][Kiwi.OutputName("count")] static uint count = 0;
  static int count1 = 0;
  [Kiwi.OutputWordPort(31, 0)][Kiwi.OutputName("elimit")] static int elimit = 0; // The main parameter (abscissa).

  // The evariant_master is also edited by a sed script that runs an individual experiment.
  // For fair comparison with mono native this needs to be a compile time constant.
    const int evariant_master = 0;
    [Kiwi.OutputWordPort(31, 0)][Kiwi.OutputName("evariant")] static int evariant_output = evariant_master;  

    [Kiwi.HardwareEntryPoint()]
    public static void Main()
    { bool kpp = true;
      elimit = limit;
      Kiwi.KppMark("START", "INITIALISE");  // Waypoint
      Console.WriteLine("Primes Up To " + limit);
      // Clear array
      
      count1 = 2; count = 0; // RESET VALUE FAILED AT ONE POINT: HENCE NEED THIS LINE
      for (int woz = 0; woz < limit; woz++) 
	{ PA[woz] = true; 
	  Console.WriteLine("Setting initial array flag to hold : addr={0} readback={1}", woz, PA[woz]); // Read back.
	}
      
      Kiwi.KppMark("wp2", "CROSSOFF"); // Waypoint
      int i, j;
      
      for (i=2;i<limit; i++)  // Can our predictor cope with the standard optimisations?
	{ // Cross off the multiples - optimise by skipping where the base is already crossed off.
	  if (evariant_master > 0)	
	    {
	      bool pp = PA[i];
	      Console.WriteLine(" tnow={2}: scanning up for live factor {0} = {1} ", i, pp,  Kiwi.tnow);
	      if (!pp)		  continue;
	      count1 += 1;
	    }
	  // Can further optimise by commencing the cross-off at the factor squared.
	  j= (evariant_master > 1) ? i*i : i+i;
	  if (j >= limit)	
	    { Console.WriteLine("Skip out on square");
	      break;
	    }
	  for (; j<limit; j+=i) 
            { Console.WriteLine("Cross off {0} {1}   (count1={2})", i, j, count1);
	      Kiwi.Pause(); PA[j] = false; 
            }
        }
      Kiwi.KppMark("wp3", "COUNTING");  // Waypoint
      Console.WriteLine("Now counting");
      // Count how many there were and store them consecutively in the output array.
      for (int w = 0; w < limit; w++) 
	{ if (PA[w]) count += 1; 
          Console.WriteLine("Tally counting {0} {1}", w, count);
	}
      Console.WriteLine("There are {0} primes below the natural number {1}.", count, limit);
    }
}

Black arcs indicate state trajectories. Blue arcs indicate operations on structural resources such as ALUs and RAMs.

»Kiwi Primes Demo Sieve of Eratosthenes
23: (C) 2008-17, DJ Greaves, University of Cambridge, Computer Laboratory.