Menu
▾
▴
[X10-commits] SF.net SVN: x10:[11574] branches/x10-1.7/pppp/src
|
From: <vj...@us...> - 2009-10-22 13:07:26
|
Revision: 11574
http://x10.svn.sourceforge.net/x10/?rev=11574&view=rev
Author: vj0
Date: 2009-10-22 13:07:18 +0000 (Thu, 22 Oct 2009)
Log Message:
-----------
Added Paths:
-----------
branches/x10-1.7/pppp/src/AllReduce.x10
branches/x10-1.7/pppp/src/Jacobi.x10
branches/x10-1.7/pppp/src/Prefix.x10
branches/x10-1.7/pppp/src/Utils.x10
Added: branches/x10-1.7/pppp/src/AllReduce.x10
===================================================================
--- branches/x10-1.7/pppp/src/AllReduce.x10 (rev 0)
+++ branches/x10-1.7/pppp/src/AllReduce.x10 2009-10-22 13:07:18 UTC (rev 11574)
@@ -0,0 +1,45 @@
+/**
+ * An implementation of allReduce for a uniquely distributed array.
+ * Uses a helper array of the same distribution.
+ *
+ * This program assumes the operation to be performed is associative and
+ * commutative.
+ *
+ * The program is safe.
+ *
+ * @author vj
+ */
+public class AllReduce {
+ static def even(p:int):Boolean = p % 2 == 0;
+ public static def allReduce(red:Array[int](1), black:Array[int](1)) {
+ val P = Place.MAX_PLACES;
+ val phases = Utils.log2(P);
+ var shift_:Int=1;
+ for ((phase) in 0..phases-1) {
+ val shift = shift_;
+ finish ateach ((p) in red.dist) {
+ val ev = even(phase);
+ val destId = (p+shift)% P;
+ val source = here;
+ val elem = ev ? black(p) : red(p);
+ at(Place.places(destId)) {
+ if (ev)
+ red(destId) = elem + black(destId);
+ else
+ black(destId) = elem + red(destId);
+ }
+ }
+ shift_ *=2;
+ }
+ return (even(phases-1)) ? red(0) : black(0);
+ }
+ public static def main(Rail[String]) {
+ assert Utils.powerOf2(Place.MAX_PLACES)
+ : " Must run on power of 2 places.";
+ val D = Dist.makeUnique();
+ val black:Array[int](1) = Array.make[int](D, (p:Point)=> p(0));
+ val red:Array[int](1) = Array.make[int](D, (Point)=> 0);
+ val result = allReduce(red, black);
+ Console.OUT.println("allReduce = " + result);
+ }
+}
\ No newline at end of file
Added: branches/x10-1.7/pppp/src/Jacobi.x10
===================================================================
--- branches/x10-1.7/pppp/src/Jacobi.x10 (rev 0)
+++ branches/x10-1.7/pppp/src/Jacobi.x10 2009-10-22 13:07:18 UTC (rev 11574)
@@ -0,0 +1,86 @@
+/*
+ *
+ * (C) Copyright IBM Corporation 2006
+ *
+ * This file is part of X10 Test.
+ *
+ */
+import harness.x10Test;
+
+/**
+ * Jacobi iteration.
+ *
+ * At each step of the iteration, replace the value of a cell with
+ * the average of its adjacent cells in the (i,j) dimensions.
+ * Compute the error at each iteration as the sum of the changes
+ * in value across the whole array. Continue the iteration until
+ * the error falls below a given bound.
+ *
+ * This program is safe.
+ *
+ * @author vj
+ * @author cvp
+ * @author kemal
+ */
+public class Jacobi {
+ const N = 6;
+ const epsilon = 0.002D;
+ const epsilon2 = 0.000000001D;
+ val R: Region(2) = [0..(N+1), 0..(N+1)];
+ val R_inner: Region(2) = [1..N, 1..N];
+ val D:Dist(2) = Dist.makeBlock(R, 0);
+ val D_inner = D.restriction(R_inner);
+ val D_Boundary = D.difference(D_inner.region);
+ const EXPECTED_ITERS: int = 97;
+ const EXPECTED_ERR: double = 0.0018673382039402497;
+ public incomplete static def read[T](x:T):Effects;
+ public incomplete static def write[T](x:T):Effects;
+ public incomplete static def touch[T](x:T):Effects;
+
+ public def run() {
+ @fun {
+ val initializer: Box[(Point)=>double]
+ = ((i,j):Point) => (i==0||i==N+1||j==0||j==N+1)? (N-1)/2
+ : (i-1)*N+(j-1) as double;
+ val a = Array.make[double](D, initializer),
+ b = Array.make[double](D, (Point)=>0.0D);
+ val error = Array.make[double](Dist.makeUnique(D.places()), (Point)=>0.0D);
+ var iters:int=0;
+ @fun(touch(a).and(touch(b)))
+ while (true) {
+ if (step(a, b, error) < epsilon)
+ break;
+ iters++;
+ if (step(b, a, error) < epsilon)
+ break;
+ iters++;
+ }
+ Console.OUT.println("Error= " + error + " iters=" + iters);
+ return iters == EXPECTED_ITERS;
+ }}
+
+ public def step(red: Array[double](2), black: Array[double](red.dist),
+ error: Array[double](1)) {
+ @fun(read(red).and(touch(black)).and(touch(error))) {
+ @fun(read(red).and(write(black)).and(write(error)))
+ finish {
+ @parfun(read(red).and(write(black)).and(write(error)))
+ for (p in red.dist.places())
+ @parfun(read(red).and(write(black|p)).and(write(error|p)))
+ async(p) {
+ val local = D_inner | p;
+ var err: double = 0.0D;
+ for ((i,j) in local) {
+ black(i,j) = (red(i+1, j)+red(i-1, j)
+ +red(i, j-1)+red(i, j+1))/4.0;
+ err = Math.max(Math.abs(black(i,j)-red(i,j)), err);
+ }
+ error(p.id)=err;
+ }
+ }
+ return error.reduce(double.+, double.MAX_VALUE);
+ }}
+ public static def main(Rail[String]) {
+ new Jacobi().run();
+ }
+}
\ No newline at end of file
Added: branches/x10-1.7/pppp/src/Prefix.x10
===================================================================
--- branches/x10-1.7/pppp/src/Prefix.x10 (rev 0)
+++ branches/x10-1.7/pppp/src/Prefix.x10 2009-10-22 13:07:18 UTC (rev 11574)
@@ -0,0 +1,47 @@
+/**
+ * Compute the parallel prefix of a uniquely distributed array.
+ * The program can be easily adapted to compute parallel prefix for a block-distributed array.
+ *
+ * This program is safe.
+ * @author vj
+ *
+ */
+public class Prefix {
+ public def run() = run(0, a.region.max(0));
+ public def run(lo:int, hi:int) {
+ if (lo+1 == hi) {
+ at (a.dist(lo)) {
+ val e = a(lo);
+ at (a.dist(hi))
+ a(hi)= e + a(hi); // preserve order
+ }
+ return;
+ }
+ val mid = lo + ((hi-lo+1)/2);
+ finish {
+ async run(lo, mid-1);
+ run(mid, hi);
+ }
+ at (a.dist(mid-1)) { //expand
+ val e = a(mid-1);
+ finish for ((p) in mid..hi) async
+ at(a.dist(p))
+ a(p) = e + a(p);
+ }
+ }
+ /**
+ * Print out the elements of the distributed array sequentially.
+ */
+ public def print() {
+ for ((p) in a.region)
+ at (a.dist(p))
+ Console.OUT.println("a(" + p+ ")= " + a(p));
+ }
+
+ public static def main(Rail[String]) {
+ assert Utils.powerOf2(Place.MAX_PLACES) : " Must run on power of 2 places.";
+ val s = new Prefix();
+ s.run();
+ s.print();
+ }
+}
\ No newline at end of file
Added: branches/x10-1.7/pppp/src/Utils.x10
===================================================================
--- branches/x10-1.7/pppp/src/Utils.x10 (rev 0)
+++ branches/x10-1.7/pppp/src/Utils.x10 2009-10-22 13:07:18 UTC (rev 11574)
@@ -0,0 +1,24 @@
+public class Utils {
+ public static def max(a:int, b:int) = a>b?a:b;
+ public static def min(a:int, b:int) = a>b?b:a;
+ public static def max(a:double, b:double) = a>b?a:b;
+ public static def min(a:double, b:double) = a>b?b:a;
+ public static def fabs(v:double) = v>=0.0?v:-v;
+ public static def FFT_Flops(n:int)= ((4.0*n-3.0)*n-1.0)*n/6.0;
+ public static def powerOf2(var p:int) {
+ if (p <=0) return false;
+ if (p==1) return true;
+ while (true) {
+ if (p%2==1) return false;
+ p /=2;
+ if (p==1) return true;
+ }
+ }
+ public static def log2(var p:int) {
+ assert powerOf2(p) : "p=" + p + " is not a power of 2";
+ if (p==1) return 0;
+ var i:int=0;
+ while (p>1) { p=p/2; i++;}
+ return i;
+ }
+}
This was sent by the SourceForge.net collaborative development platform, the world's largest Open Source development site.
|