Mercurial > hg > Database > Alice
changeset 202:7f47231ef509 working
add new flip API
line wrap: on
line diff
--- a/.settings/org.eclipse.core.resources.prefs Sat Mar 23 17:07:59 2013 +0900 +++ b/.settings/org.eclipse.core.resources.prefs Mon Mar 25 17:46:07 2013 +0900 @@ -1,3 +1,3 @@ eclipse.preferences.version=1 encoding//src/alice/test/codesegment/local/bitonicsort/SortTest.java=UTF-8 -encoding//src/alice/test/codesegment/local/bitonicsort/nolist/SortTest.java=UTF-8 +encoding//src/alice/test/codesegment/local/bitonicsort/noarrraylist/SortTest.java=UTF-8
--- a/src/alice/codesegment/InputDataSegment.java Sat Mar 23 17:07:59 2013 +0900 +++ b/src/alice/codesegment/InputDataSegment.java Mon Mar 25 17:46:07 2013 +0900 @@ -4,6 +4,7 @@ import org.msgpack.type.Value; +import alice.datasegment.Command; import alice.datasegment.CommandType; import alice.datasegment.DataSegment; import alice.datasegment.DataSegmentValue; @@ -21,7 +22,7 @@ private AtomicInteger count = new AtomicInteger(1); // 1 for no input data segments private AtomicInteger keyCount = new AtomicInteger(0); // number of DataSegments - private DataSegmentValue dsv; + private Command cmd; public InputDataSegment(CodeSegment cs) { this.cs = cs; @@ -59,12 +60,9 @@ DataSegment.getLocal().take(receiver, key, index, cs); } - public void flip(Receiver receiver, String key){ - - } - - public void flip(Receiver receiver, Value val, Object obj){ - DataSegment.getLocal().flip(receiver.key, val, obj, dsv); + public void flip(CommandType type, String key, Value val,Object obj) { + cmd.setElement(type, key, val, obj); + DataSegment.getLocal().flip(cmd); } public void reply(Receiver receiver, DataSegmentValue val) { @@ -72,7 +70,6 @@ receiver.val = val.val; receiver.from = val.from; receiver.obj = val.obj; - setDataSegmentValue(val); receive(); } @@ -102,8 +99,14 @@ return new Receiver(this, type); } - private void setDataSegmentValue(DataSegmentValue dsv){ - this.dsv = dsv; + public void setCommand(Command cmd) { + this.cmd = cmd; + } + + public void reply(Receiver receiver, int index, Value val, Object obj, + String reverseKey) { + // TODO Auto-generated method stub + } }
--- a/src/alice/datasegment/Command.java Sat Mar 23 17:07:59 2013 +0900 +++ b/src/alice/datasegment/Command.java Mon Mar 25 17:46:07 2013 +0900 @@ -16,14 +16,7 @@ public CodeSegment cs; public String reverseKey; public Object obj; - public DataSegmentValue dsv; - - public Command(CommandType cmdType, int seq, DataSegmentValue dsv){ - this.type=cmdType; - this.seq=seq; - this.dsv=dsv; - } - + public Command(CommandType cmdType, Receiver receiver, String key, Value val, int index, int seq, BlockingQueue<Command> replyQueue, CodeSegment cs, String reverseKey) { this.type = cmdType; this.receiver = receiver; @@ -60,9 +53,6 @@ this.reverseKey = reverseKey; } - - - public String getCommandString() { String csName = "null"; if (cs != null) { @@ -71,4 +61,15 @@ return this.type + "\t" + key + "\t" + val + "\tindex=" + index + "\tcs=" + csName; } + public void setElement(CommandType cmdType, String key, Value val, Object obj){ + this.type = cmdType; + this.receiver = null; + this.key = key; + this.val = val; + this.obj = obj; + this.replyQueue = null; + this.cs = null; + this.reverseKey = "local"; + } + }
--- a/src/alice/datasegment/CommandType.java Sat Mar 23 17:07:59 2013 +0900 +++ b/src/alice/datasegment/CommandType.java Mon Mar 25 17:46:07 2013 +0900 @@ -10,8 +10,7 @@ REMOVE, REPLY, CLOSE, - FINISH, - FLIP; + FINISH; public int id; public static HashMap<Integer, CommandType> hash = new HashMap<Integer, CommandType>();
--- a/src/alice/datasegment/DataSegmentKey.java Sat Mar 23 17:07:59 2013 +0900 +++ b/src/alice/datasegment/DataSegmentKey.java Mon Mar 25 17:46:07 2013 +0900 @@ -17,14 +17,6 @@ private ArrayList<Command> waitList = new ArrayList<Command>(); private AtomicInteger tailIndex = new AtomicInteger(1); - public int getIndex(){ - return tailIndex.getAndIncrement(); - } - - public synchronized int getWaitListSize(){ - return waitList.size(); - } - public void runCommand(Command cmd) { switch (cmd.type) { case UPDATE: @@ -40,8 +32,7 @@ Command waitCmd = iter.next(); if (waitCmd.index < index) { try { - //waitCmd.replyQueue.put(new Command(CommandType.REPLY, null, null, cmd.val, cmd.obj, index, waitCmd.seq, null, null, cmd.reverseKey)); - waitCmd.replyQueue.put(new Command(CommandType.REPLY, waitCmd.seq, dsv)); + waitCmd.replyQueue.put(new Command(CommandType.REPLY, null, null, cmd.val, cmd.obj, index, waitCmd.seq, null, null, cmd.reverseKey)); } catch (InterruptedException e) { e.printStackTrace(); } @@ -62,8 +53,7 @@ for (DataSegmentValue data : dataList) { if (data.index > cmd.index) { try { - //cmd.replyQueue.put(new Command(CommandType.REPLY, null, null, data.val, data.obj, data.index, cmd.seq, null, null, data.from)); - cmd.replyQueue.put(new Command(CommandType.REPLY, cmd.seq, data)); + cmd.replyQueue.put(new Command(CommandType.REPLY, null, null, data.val, data.obj, data.index, cmd.seq, null, null, data.from)); } catch (InterruptedException e) { e.printStackTrace(); } @@ -84,8 +74,7 @@ DataSegmentValue data = iter.next(); if (data.index > cmd.index) { try { - //cmd.replyQueue.put(new Command(CommandType.REPLY, null, null, data.val, data.obj, data.index, cmd.seq, null, null, data.from)); - cmd.replyQueue.put(new Command(CommandType.REPLY, cmd.seq, data)); + cmd.replyQueue.put(new Command(CommandType.REPLY, null, null, data.val, data.obj, data.index, cmd.seq, null, null, data.from)); } catch (InterruptedException e) { e.printStackTrace(); } @@ -97,25 +86,6 @@ if (waitFlag) waitList.add(cmd); break; - case FLIP: - // check waitList - index = cmd.dsv.index; - for (Iterator<Command> iter = waitList.iterator(); iter.hasNext(); ) { - Command waitCmd = iter.next(); - if (waitCmd.index < index) { - try { - waitCmd.replyQueue.put(new Command(CommandType.REPLY, waitCmd.seq, cmd.dsv)); - } catch (InterruptedException e) { - e.printStackTrace(); - } - iter.remove(); - if (waitCmd.type == CommandType.TAKE) { - dataList.remove(cmd.dsv); - break; - } - } - } - break; case REMOVE: // TODO: implements later break;
--- a/src/alice/datasegment/DataSegmentManager.java Sat Mar 23 17:07:59 2013 +0900 +++ b/src/alice/datasegment/DataSegmentManager.java Mon Mar 25 17:46:07 2013 +0900 @@ -28,8 +28,8 @@ continue; } seqHash.remove(reply.seq); - //cmd.cs.ids.reply(cmd.receiver, new DataSegmentValue(reply.index, reply.val, reply.obj, reply.reverseKey)); - cmd.cs.ids.reply(cmd.receiver, reply.dsv); + cmd.cs.ids.reply(cmd.receiver, reply.index, reply.val, reply.obj, reply.reverseKey); + cmd.cs.ids.setCommand(cmd); if (logger.isDebugEnabled()) logger.debug(reply.getCommandString() + " " + cmd.getCommandString()); } catch (InterruptedException e) {
--- a/src/alice/datasegment/DataSegmentValue.java Sat Mar 23 17:07:59 2013 +0900 +++ b/src/alice/datasegment/DataSegmentValue.java Mon Mar 25 17:46:07 2013 +0900 @@ -22,10 +22,4 @@ this.from = reverseKey; } - public synchronized void setValue(int index, Value val, Object obj){ - this.index = index; - this.val = val; - this.obj = obj; - } - }
--- a/src/alice/datasegment/LocalDataSegmentManager.java Sat Mar 23 17:07:59 2013 +0900 +++ b/src/alice/datasegment/LocalDataSegmentManager.java Mon Mar 25 17:46:07 2013 +0900 @@ -62,7 +62,7 @@ @Override public void put(String key, Value val) { DataSegmentKey dataSegmentKey = getDataSegmentKey(key); - Command cmd = new Command(CommandType.PUT, null, key, val, 0, 0, replyQueue, null, reverseKey); + Command cmd = new Command(CommandType.PUT, null, key, val, 0, 0, null, null, reverseKey); addCommand(dataSegmentKey, cmd); if (logger.isDebugEnabled()) logger.debug(cmd.getCommandString()); @@ -70,7 +70,7 @@ public void put(String key, Object obj) { DataSegmentKey dataSegmentKey = getDataSegmentKey(key); - Command cmd = new Command(CommandType.PUT, null, key, obj, 0, 0, replyQueue, null, reverseKey); + Command cmd = new Command(CommandType.PUT, null, key, obj, 0, 0, null, null, reverseKey); addCommand(dataSegmentKey, cmd); if (logger.isDebugEnabled()) logger.debug(cmd.getCommandString()); @@ -82,7 +82,7 @@ @Override public void update(String key, Value val) { DataSegmentKey dataSegmentKey = getDataSegmentKey(key); - Command cmd = new Command(CommandType.UPDATE, null, key, val, 0, 0, replyQueue, null, reverseKey); + Command cmd = new Command(CommandType.UPDATE, null, key, val, 0, 0, null, null, reverseKey); addCommand(dataSegmentKey, cmd); if (logger.isDebugEnabled()) logger.debug(cmd.getCommandString()); @@ -90,7 +90,7 @@ public void update(String key, Object val) { DataSegmentKey dataSegmentKey = getDataSegmentKey(key); - Command cmd = new Command(CommandType.UPDATE, null, key, val, 0, 0, replyQueue, null, reverseKey); + Command cmd = new Command(CommandType.UPDATE, null, key, val, 0, 0, null, null, reverseKey); addCommand(dataSegmentKey, cmd); if (logger.isDebugEnabled()) logger.debug(cmd.getCommandString()); @@ -136,17 +136,11 @@ } - public void flip(String key ,Value val, Object obj, DataSegmentValue dsv) { - DataSegmentKey dataSegmentKey = getDataSegmentKey(key); - int index = dataSegmentKey.getIndex(); - dsv.setValue(index, val, obj); - if (dataSegmentKey.getWaitListSize()!=0){ - Command cmd = new Command(CommandType.FLIP, 0, dsv); - addCommand(dataSegmentKey, cmd); - if (logger.isDebugEnabled()) - logger.debug(cmd.getCommandString()); - } - + public void flip(Command cmd){ + DataSegmentKey dataSegmentKey = getDataSegmentKey(cmd.key); + addCommand(dataSegmentKey, cmd); + if (logger.isDebugEnabled()) + logger.debug(cmd.getCommandString()); } }
--- a/src/alice/datasegment/Receiver.java Sat Mar 23 17:07:59 2013 +0900 +++ b/src/alice/datasegment/Receiver.java Mon Mar 25 17:46:07 2013 +0900 @@ -31,12 +31,12 @@ ids.regist(); } - public void flip(Value val){ - ids.flip(this, val, null); + public void flip(CommandType type, String key, Object obj){ + ids.flip(type, key, null, obj); } - public void flip(Object obj) { - ids.flip(this, null, obj); + public void flip(CommandType type, String key, Value val){ + ids.flip(type, key, val, null); } public void setKey(String managerKey, String key) {
--- a/src/alice/test/codesegment/api/FlipTest.java Sat Mar 23 17:07:59 2013 +0900 +++ b/src/alice/test/codesegment/api/FlipTest.java Mon Mar 25 17:46:07 2013 +0900 @@ -22,23 +22,25 @@ @Override public void run() { if (flag){ - System.out.println(System.currentTimeMillis() - t); + System.out.println(System.currentTimeMillis() - t ); //System.out.println(" "+arg1.obj+" "+arg1.index); - if (count >= 100) System.exit(0); - flag = false; - count++; - new FlipCodeSegment(Long.toString(t)).execute(); + //if (count >= 100) + System.exit(0); + //flag = false; + //count++; + //new FlipCodeSegment(Long.toString(t)).execute(); } else { t = System.currentTimeMillis(); - for (int i = 0;i<1000000;i++){ + for (int i = 0;i<100000;i++){ + Integer num = i; - arg1.flip(num); + arg1.flip(CommandType.UPDATE, arg1.key, num); //ods.update(arg1.key, num, false); } flag = true; - new FlipTest(arg1.key ,1000000); + new FlipTest(arg1.key,100000); } }
--- a/src/alice/test/codesegment/local/bitonicsort/EvenPhase.java Sat Mar 23 17:07:59 2013 +0900 +++ b/src/alice/test/codesegment/local/bitonicsort/EvenPhase.java Mon Mar 25 17:46:07 2013 +0900 @@ -40,7 +40,6 @@ RangeInfo info = info0.asClass(RangeInfo.class); int sort_count = info5.asInteger(); int count = info6.asInteger(); - System.out.println(info.range); if (info2==null){ DataList list = (DataList)info1.obj; if (count > sort_count){
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/src/alice/test/codesegment/local/bitonicsort/noarrraylist/DataInfo.java Mon Mar 25 17:46:07 2013 +0900 @@ -0,0 +1,16 @@ +package alice.test.codesegment.local.bitonicsort.noarrraylist; + +import org.msgpack.annotation.Message; + +@Message +public class DataInfo { + public int index; + public int ptr; + + public DataInfo(){} + + public DataInfo(int _index, int _ptr){ + index = _index; + ptr = _ptr; + } +}
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/src/alice/test/codesegment/local/bitonicsort/noarrraylist/DataList.java Mon Mar 25 17:46:07 2013 +0900 @@ -0,0 +1,40 @@ +package alice.test.codesegment.local.bitonicsort.noarrraylist; + +import org.msgpack.annotation.Message; + +@Message +public class DataList { + + public int[] table; + + public DataList(int size){ + table = new int[size]; + } + + public DataList(int[] numbers){ + table = numbers; + } + + public DataList createDataList(int start, int size){ + int[] table2 = new int[size]; + for (int i=start,j=0;i<(start+size);i++,j++){ + table2[j] = table[i]; + } + return new DataList(table2); + } + + public void swap(int i, int j){ + int tmp = table[i]; + table[i] = table[j]; + table[j] = tmp; + } + + public void showData(){ + for(int i = 0;i<table.length;i++){ + System.out.print(table[i]+ " "); + + } + System.out.println(); + } + +}
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/src/alice/test/codesegment/local/bitonicsort/noarrraylist/EvenPhase.java Mon Mar 25 17:46:07 2013 +0900 @@ -0,0 +1,84 @@ +package alice.test.codesegment.local.bitonicsort.noarrraylist; + +import alice.codesegment.CodeSegment; +import alice.datasegment.CommandType; +import alice.datasegment.Receiver; + +public class EvenPhase extends CodeSegment{ + private Receiver info0 = ids.create(CommandType.PEEK); // range + private Receiver info1; // Array1 + private Receiver info2; // Array2 + private Receiver info3 = ids.create(CommandType.PEEK); // block_num + private Receiver info4 = ids.create(CommandType.PEEK); // last_block_num + private Receiver info5 = ids.create(CommandType.PEEK); // sort_count + private Receiver info6 = ids.create(CommandType.TAKE); // count + + public EvenPhase(String key0 ,String key1 ,int index,String key6){ + info0.setKey(key0); + info1 = ids.create(CommandType.TAKE); + info1.setKey(key1,index); + info3.setKey("block_num"); + info4.setKey("last_block_num"); + info5.setKey("sort_count"); + info6.setKey(key6); + } + + public EvenPhase(String key0,String key1,String key2,int index,String key6){ + info0.setKey(key0); + info1 = ids.create(CommandType.TAKE); + info1.setKey(key1,index); + info2 = ids.create(CommandType.TAKE); + info2.setKey(key2,index); + info3.setKey("block_num"); + info4.setKey("last_block_num"); + info5.setKey("sort_count"); + info6.setKey(key6); + } + + @Override + public void run() { + RangeInfo info = info0.asClass(RangeInfo.class); + int sort_count = info5.asInteger(); + int count = info6.asInteger(); + + if (info2==null){ + DataList list = (DataList)info1.obj; + if (count > sort_count){ + ods.update("array"+info.range, list ,false); + return; + } + ods.put(info.range+"f", "dummy"); + ods.put(info.range+"b", list, false); + //System.out.println("next Odd "+info.range+" "+info.range+"b"+" "+(info.range+1)+"f"); + new OddPhase(info0.key,info.range+"b",(info.range+1)+"f",count,info6.key); + } else { + DataList list1 = (DataList)info1.obj; + DataList list2 = (DataList)info2.obj; + + DataList list3 = new DataList(list1.table.length+list2.table.length); + System.arraycopy(list1.table, 0, list3.table, 0, list1.table.length); + System.arraycopy(list2.table, 0, list3.table, list1.table.length, list2.table.length); + + if (count > sort_count){ + ods.update("array"+info.range, list3 ,false); + return; + } + int block_num = info3.asInteger(); + Sort.quickSort(list3, 0, list3.table.length-1); + if (!info.lastFlag){ + ods.put(info.range+"f", list3.createDataList(0, block_num/2) ,false); + ods.put(info.range+"b", list3.createDataList(block_num/2, block_num/2),false); + //System.out.println("next Odd "+info.range+" "+ info.range+"b"+" "+(info.range+1)+"f"); + new OddPhase(info0.key,info.range+"b",(info.range+1)+"f",count,info6.key); + } else { + int last_block_num = info4.asInteger(); + ods.put(info.range+"f", list3.createDataList(0, block_num/2) ,false); + ods.put(info.range+"b", list3.createDataList(block_num/2, last_block_num) ,false); + //System.out.println("next Odd "+info.range+" "+ info.range+"b"); + new OddPhase(info0.key ,info.range+"b",count,info6.key); + } + + } + ods.update(info6.key, count+1); + } +}
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/src/alice/test/codesegment/local/bitonicsort/noarrraylist/LocalBitonicSort.java Mon Mar 25 17:46:07 2013 +0900 @@ -0,0 +1,13 @@ +package alice.test.codesegment.local.bitonicsort.noarrraylist; + +import alice.daemon.AliceDaemon; +import alice.daemon.Config; + +public class LocalBitonicSort { + public static void main(String[] args){ + new AliceDaemon(new Config(args)).listen(); // logger off + + SortConfig conf = new SortConfig(args); + new SetInfo(conf).execute(); + } +}
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/src/alice/test/codesegment/local/bitonicsort/noarrraylist/MakeData.java Mon Mar 25 17:46:07 2013 +0900 @@ -0,0 +1,30 @@ +package alice.test.codesegment.local.bitonicsort.noarrraylist; + +import java.util.Random; + +import alice.codesegment.CodeSegment; +import alice.datasegment.CommandType; +import alice.datasegment.Receiver; + +public class MakeData extends CodeSegment { + + private Receiver info1 = ids.create(CommandType.PEEK); + private Receiver info2 = ids.create(CommandType.TAKE); + + public MakeData(){ + info1.setKey("sortconf"); + info2.setKey("data"); + } + + @Override + public void run() { + SortConfig conf = info1.asClass(SortConfig.class); + DataList list = (DataList)info2.obj; + int size = conf.getLength(); + Random rnd = new Random(); + for (int i = 0; i < size; i++){ + list.table[i] = rnd.nextInt(100000); + } + ods.update("list", list, false); + } +}
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/src/alice/test/codesegment/local/bitonicsort/noarrraylist/OddPhase.java Mon Mar 25 17:46:07 2013 +0900 @@ -0,0 +1,96 @@ +package alice.test.codesegment.local.bitonicsort.noarrraylist; + +import alice.codesegment.CodeSegment; +import alice.datasegment.CommandType; +import alice.datasegment.Receiver; + +public class OddPhase extends CodeSegment{ + private Receiver info0 = ids.create(CommandType.PEEK); // range + private Receiver info1; // Array1 + private Receiver info2; // Array2 + private Receiver info3 = ids.create(CommandType.PEEK); // block_num + //private Receiver info4 = ids.create(CommandType.PEEK); // last_block_num + private Receiver info5 = ids.create(CommandType.PEEK); // sort_count + private Receiver info6 = ids.create(CommandType.TAKE); // count + + public OddPhase(String key0 ,String key1 ,int index,String key6){ + info0.setKey(key0); + info1 = ids.create(CommandType.TAKE); + info1.setKey(key1,index); + info3.setKey("block_num"); + info5.setKey("sort_count"); + info6.setKey(key6); + } + + public OddPhase(String key0,String key1,String key2,int index,String key6){ + info0.setKey(key0); + info1 = ids.create(CommandType.TAKE); + info1.setKey(key1,index); + info2 = ids.create(CommandType.TAKE); + info2.setKey(key2,index); + info3.setKey("block_num"); + info5.setKey("sort_count"); + info6.setKey(key6); + } + + @Override + public void run() { + RangeInfo info = info0.asClass(RangeInfo.class); + int block_num = info3.asInteger(); + int sort_count = info5.asInteger(); + int count = info6.asInteger(); + //System.out.println("count is " +count); + if (info2==null){ + DataList list = (DataList)info1.obj; + if (count > sort_count){ + ods.update("array"+info.range, list, false); + return; + } + Sort.quickSort(list,0,list.table.length-1); + if (!info.lastFlag){ + ods.put(info.range+"f", list.createDataList(0, block_num/2) ,false); + ods.put(info.range+"b", list.createDataList(block_num/2, block_num/2) ,false); + + if (info.range==0){ + //System.out.println("next Even "+info.range+" "+info.range+"f"); + new EvenPhase(info0.key,info.range+"f",count,info6.key); + } else { + //System.out.println("next Even "+info.range+" "+ (info.range-1)+"b"+" "+(info.range)+"f"); + new EvenPhase(info0.key,(info.range-1)+"b",info.range+"f",count,info6.key); + } + } else { + ods.put(info.range+"f",list, false); + ods.put(info.range+"b","dummy"); + //System.out.println("next Even "+info.range+" "+ (info.range-1)+"b"+" "+(info.range)+"f"); + new EvenPhase(info0.key,(info.range-1)+"b",info.range+"f",count,info6.key); + } + + } else { + DataList list1 = (DataList)info1.obj; + DataList list2 = (DataList)info2.obj; + + DataList list3 = new DataList(list1.table.length+list2.table.length); + System.arraycopy(list1.table, 0, list3.table, 0, list1.table.length); + System.arraycopy(list2.table, 0, list3.table, list1.table.length, list2.table.length); + + if (count > sort_count){ + ods.update("array"+info.range, list3, false); + return; + } + + Sort.quickSort(list3,0,list3.table.length-1); + ods.put(info.range+"f", list3.createDataList(0, block_num/2) ,false); + ods.put(info.range+"b", list3.createDataList(block_num/2, block_num/2) ,false); + + if (info.range==0){ + //System.out.println("next Even2b "+info.range+" "+ info.range+"f"); + new EvenPhase(info0.key,info.range+"f",count,info6.key); + } else { + //System.out.println("next Even2b "+info.range+" "+ (info.range-1)+"b"+" "+info.range+"f"); + new EvenPhase(info0.key,(info.range-1)+"b",info.range+"f",count,info6.key); + } + } + ods.update(info6.key, count+1); + } + +}
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/src/alice/test/codesegment/local/bitonicsort/noarrraylist/RangeInfo.java Mon Mar 25 17:46:07 2013 +0900 @@ -0,0 +1,16 @@ +package alice.test.codesegment.local.bitonicsort.noarrraylist; + +import org.msgpack.annotation.Message; + +@Message +public class RangeInfo { + public int range; + public boolean lastFlag; + + public RangeInfo(){} + public RangeInfo(int i,boolean flag){ + range = i; + lastFlag = flag; + } + +}
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/src/alice/test/codesegment/local/bitonicsort/noarrraylist/SetInfo.java Mon Mar 25 17:46:07 2013 +0900 @@ -0,0 +1,22 @@ +package alice.test.codesegment.local.bitonicsort.noarrraylist; + +import alice.codesegment.CodeSegment; + +public class SetInfo extends CodeSegment { + + private SortConfig conf; + public SetInfo(SortConfig conf) { + this.conf = conf; + } + + @Override + public void run() { + ods.put("sortconf", conf); + ods.put("data", new DataList(conf.length), false); + + new MakeData(); + new SetTask(); + } + + +}
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/src/alice/test/codesegment/local/bitonicsort/noarrraylist/SetTask.java Mon Mar 25 17:46:07 2013 +0900 @@ -0,0 +1,55 @@ +package alice.test.codesegment.local.bitonicsort.noarrraylist; + +import alice.codesegment.CodeSegment; +import alice.datasegment.CommandType; +import alice.datasegment.Receiver; + +public class SetTask extends CodeSegment { + public static long t; + private Receiver info1 = ids.create(CommandType.PEEK); + private Receiver info2 = ids.create(CommandType.TAKE); + + SetTask(){ + info1.setKey("sortconf"); + info2.setKey("list"); + } + + @Override + public void run() { + SortConfig conf = info1.asClass(SortConfig.class); + DataList list = (DataList)info2.obj; + + int sort_count = conf.getSplitNum(); + ods.put("sort_count", sort_count*2); + + int block_num = (conf.getLength() + conf.getSplitNum() - 1 ) / sort_count; + ods.put("block_num", block_num); + int last_block_num = conf.getLength() - (conf.getSplitNum() - 1)*block_num; + ods.put("last_block_num", last_block_num); + + System.out.println("sort start"); + t = System.currentTimeMillis(); + + { + String key = "array"; + int i = 0; + for (i = 0;i< conf.getSplitNum()-1; i++){ + ods.put("range"+i, new RangeInfo(i,false)); + ods.update(key+i, list.createDataList(i*block_num, block_num) ,false); + ods.update("count"+i, 0); + new OddPhase("range"+i,key+i,0,"count"+i); + } + + ods.put("range"+i, new RangeInfo(i,true)); + ods.update(key+i, list.createDataList(i*block_num, last_block_num) ,false); + ods.update("count"+i, 0); + ods.put("arraynum",i+1); + new OddPhase("range"+i,key+i,0,"count"+i); + new ShowData(i+1); + + } + + + } + +}
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/src/alice/test/codesegment/local/bitonicsort/noarrraylist/ShowData.java Mon Mar 25 17:46:07 2013 +0900 @@ -0,0 +1,48 @@ +package alice.test.codesegment.local.bitonicsort.noarrraylist; + +import alice.codesegment.CodeSegment; +import alice.datasegment.CommandType; +import alice.datasegment.Receiver; + +public class ShowData extends CodeSegment{ + + private Receiver[] info; + private Receiver info0 = ids.create(CommandType.PEEK); + + public ShowData(int cnt) { + info = new Receiver[cnt]; + for (int i= 0;i < cnt; i++) + info[i] = ids.create(CommandType.PEEK); + for (int i= 0;i < cnt; i++) + info[i].setKey("array"+i,1); + + info0.setKey("arraynum"); + } + + @Override + public void run() { + System.out.println(System.currentTimeMillis() -SetTask.t +" ms"); + int cnt = info0.asInteger(); + int size = 0; + + for (int i= 0;i < cnt; i++){ + DataList dlist = (DataList)info[i].obj; + size += dlist.table.length; + } + + DataList list = new DataList(size); + + int start = 0; + for (int i= 0;i < cnt; i++){ + DataList dlist = (DataList)info[i].obj; + System.arraycopy(dlist.table, 0, list.table, start, dlist.table.length); + start += dlist.table.length; + } + + System.out.println("size check :"+ list.table.length); + Sort.check(list); + System.exit(0); + } + + +}
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/src/alice/test/codesegment/local/bitonicsort/noarrraylist/Sort.java Mon Mar 25 17:46:07 2013 +0900 @@ -0,0 +1,62 @@ +package alice.test.codesegment.local.bitonicsort.noarrraylist; + +public class Sort { + + // this method has "stack overflow" problem + public static void quickSort(DataList data, int begin,int end){ + int[] stack = new int[1024]; + int sp = 0; + int p = 0; + while(true){ + while(begin < end){ + if (end-begin< 150){ + bubbleSort(data,begin,end); + break; + } else { + int where = (begin+end)/2; + int pivot = data.table[where]; + data.table[where] = data.table[begin]; + p = begin; + for (int i=begin+1;i<=end;i++){ + if (data.table[i]<pivot){ + p++; + if (i!=p)data.swap(p,i); + } + } + data.table[begin] = data.table[p]; + data.table[p] = pivot; + stack[sp++] = p+1; + stack[sp++] = end; + end=p-1; + } + } + if (sp==0) return; + end = stack[--sp]; + begin = stack[--sp]; + + } + } + + public static void bubbleSort(DataList data ,int begin,int end){ + for (int i=begin;i<end;i++){ + for (int j=end;j>i;j--){ + if (data.table[i] > data.table[j]){ + data.swap(i,j); + } + } + } + + + } + + public static void check(DataList data){ + System.out.println("checking ...."); + for (int i = 0; i< data.table.length-1; i++){ + if (data.table[i] > data.table[i+1]){ + System.out.println("MISS "+data.table[i]+" > "+data.table[i+1]+"Position is "+i); + return; + } + } + System.out.println("sort is succeed"); + } +}
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/src/alice/test/codesegment/local/bitonicsort/noarrraylist/SortConfig.java Mon Mar 25 17:46:07 2013 +0900 @@ -0,0 +1,39 @@ +package alice.test.codesegment.local.bitonicsort.noarrraylist; + +import org.msgpack.annotation.Message; + +@Message +public class SortConfig { + public int length = 1200; + public int MAX_BLOCK_SIZE = 1024; + public int cpu = 1; + + public SortConfig(){} + + public SortConfig(String[] args){ + for (int i=0;i<args.length; i++){ + if ("-l".equals(args[i])){ + length = Integer.parseInt(args[++i]); + } else if ("-b".equals(args[i])){ + MAX_BLOCK_SIZE = Integer.parseInt(args[++i]); + } + } + if (length<MAX_BLOCK_SIZE) MAX_BLOCK_SIZE = length; + } + + public int getLength() { + return length; + } + + public int getblockSize() { + return MAX_BLOCK_SIZE; + } + + public int getSplitNum(){ + if (length / cpu < MAX_BLOCK_SIZE){ + return cpu; + } else { + return (length + MAX_BLOCK_SIZE -1) / MAX_BLOCK_SIZE; + } + } +}
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/src/alice/test/codesegment/local/bitonicsort/noarrraylist/SortTest.java Mon Mar 25 17:46:07 2013 +0900 @@ -0,0 +1,34 @@ +package alice.test.codesegment.local.bitonicsort.noarrraylist; + +import java.util.Random; + +public class SortTest { + + public static void main(String args[]){ + int size = 10; + int MAX = 100; + long t; + DataList list1 = new DataList(size); + DataList list2 = new DataList(size); + + Random rnd = new Random(); + for (int i = 0; i < size; i++){ + int num = rnd.nextInt(MAX); + list1.table[i] = num; + list2.table[i] = num; + } + + // stack type quicksort + t = System.currentTimeMillis(); + Sort.quickSort(list1,0,list1.table.length-1); + System.out.println("quick sort3 : "+ (System.currentTimeMillis()-t)+" ms"); + Sort.check(list1); + + t = System.currentTimeMillis(); + Sort.bubbleSort(list2,0,list2.table.length-1); + System.out.println("bubble sort : "+ (System.currentTimeMillis()-t)+" ms"); + Sort.check(list2); + + + } +}