results_feedback.rtf

{\rtf1\ansi\ansicpg1252\cocoartf1348\cocoasubrtf170
{\fonttbl\f0\fswiss\fcharset0 Helvetica;\f1\froman\fcharset0 TimesNewRomanPSMT;}
{\colortbl;\red255\green255\blue255;\red0\green60\blue82;\red0\green90\blue124;}
\paperw11900\paperh16840\margl1440\margr1440\vieww19000\viewh20180\viewkind0
\deftab720
\pard\pardeftab720

\f0\fs24 \cf0 \expnd0\expndtw0\kerning0
GENERAL FEEDBACK test\
\
Some of the solutions opted to share the Graph between threads, and use \
some form of synchronization on the post() function. This is not a good \
idea, as post() forms a large part of the execution time, and \
synchronizing on this one method for multiple threads does not scale.\
	- workers already use their own graphs\
\
Note that the graph is generated on-the-fly: the Graph object does \
not consume much memory, since it only contains an implicit description \
of how to generate the actual graph. Traversal of the graph (by calling\
the post() function) can be done independently by each thread.\
	- workers already create their own graph\
\
Therefore, we ask you to give each thread a separate instance of Graph, \
by calling createGraph() of the factory multiple times. This will \
increase the potential scaling of your implementation tremendously. Add \
this improvement to all your implementations.\
	- workers already create their own graph\
\
Note that this improvement will not count as one of the required \
optimizations. The required optimizations should focus on the storage \
and sharing of state information (colors and counters). Changes to the \
algorithm itself are not allowed! In particular: the allred and early \
cycle detection extensions do not count as optimizations.\
	- we need to think of some optimizations later on\
\
Some solutions mentioned generating the complete Graph first and then \
performing the algorithm. This is incorrect. The assumption for this \
algorithm is that some of the graphs are too large to keep in memory and \
that they need to be searched for cycles on-the-fly.\
	- not relevant\
\
Terminating the other threads, when a thread found a cycle, poses a \
problem. We do not allow Thread.stop() as this is not safe. We advise \
you to use ExecutorCompletionService or even simpler ExectorService.\
Thread.interrupt may also be an option, but requires threads to check\
whether they are interrupted.\
	- maybe notifyAll (but they should be waiting then which isn\'92t the case), we need something to tell the other threads they found a cycle\
\
Many designs missed details on how to minimize the possibility of \
threads searching the same area of the graph. Sharing the red color is \
not enough. Think about the details of handling the results of the post \
function and explain your choice(s) in your evaluation. Keep in mind \
that it is impossible to prevent all overlap between threads.\
	- red is not enough, probably permutation thing\
\
Be aware that dividing the results of the post() function over the \
different threads, i.e. partitioning the post states, is incorrect. It \
would change the given algorithm. The solution is described in the \
paper: think about how you can create permutations of the list of states \
returned by the post() function.\
	- find out about permutations\
\
You will probably be using some form of hashmap to store state \
information. Many of you correctly indicated how data (colors and \
counters) for individual states can be stored and accessed concurrently. \
Pay attention however when adding this information to the hashmap for \
new states, since this can still cause race conditions.\
	- probably put IfAbsent is nice, or make a synchronized block, should be atomic either way\
\
For the evaluation document, keep in mind that you need to support your \
statements. Stating expected performance without any sort of underlying \
reasoning is meaningless. How did you come to your conclusions?\
	 - later\
\
Last but not least: do not be afraid to ask questions! We only received\
a couple of questions so far.\
\
PACKAGING\
\
Please submit the design and evaluation documents in PDF format. Your program\
sources should be compressed in a single zip archive. You can zip your src\
directory which should then replace the one in the skeleton. It should then\
compile and run using the scripts and build.xml in the skeleton.\
Alternatively, you can zip your whole program tree. Either way, we should\
easily be able to compile and run your program, using "ant" and the supplied\
shell-script.\
	- update design and stay in sync\
\
SPECIFIC FEEDBACK FOR YOUR SUBMISSION\
\
Design\
\'a0- Storing states in an ArrayList might not be a good idea.\
\'a0- It is not necessary to 'search through successors'. All mentions of\
\'a0\'a0\'a0successors in the algorithm deal with looping over all direct successors t\
\'a0\'a0\'a0for a given state s.\
\'a0- Note that the 'volatile' and 'synchronized' keywords have very different\
\'a0\'a0\'a0semantics in Java. They are not interchangeable!\
\'a0- Lack of a clear explanation on what data structures are used.\
\'a0- Storing the variable 'red' in an array is generally a bad idea. What are\
\'a0\'a0\'a0the indices of the array going to be? How can the value of 'red' for any\
\'a0\'a0\'a0given state be retrieved?\
\'a0- Good analysis on performance.\
\'a0- The proposed solutions to terminating the search are not fundamentally\
\'a0\'a0\'a0different. Both solve this by setting a value and checking it once every\
\'a0\'a0\'a0while. The StackOverflow solution is incomplete. There are other ways to\
\'a0\'a0\'a0notify threads in Java.\
\
Implementation\
\'a0- Each Worker creates its own Graph object. This is good but conflicts\
\'a0\'a0\'a0with the described solution in the design.\
	- design sync\
\'a0- Usage of ConcurrentHashMap for count (which is good), conflicts with the\
\'a0\'a0\'a0design document.\
	- design sync\
\'a0- There are race conditions in NNDFS.incrementCount(). Consider what could\
\'a0\'a0\'a0happen when one thread becomes slow after get()ing the atomicCounter\
\'a0\'a0\'a0(NNDFS/ln55) and setting a new one (NNDFS/ln59). Checking again for\
\'a0\'a0\'a0whether atomicCounter is null should not be necessary. Same holds for\
\'a0\'a0\'a0NNDFS.decrementCount().\
	- putIfAbsent is atomic, use this \cf2 *done with sync block -check the sync blocks out- !!!or some other mthd for increment and decr\cf0 \
\'a0- access() appears to consist of operations that should go in a constructor. \
\'a0- There's a race condition in setting a new AtomicCounter in Worker/ln38-41.\
\'a0\'a0\'a0Checking whether the value exists and setting a new counter if it doesn't,\
\'a0\'a0\'a0should be an atomic operation.\
	- maybe putIfAbsent solves this if it\'92s atomic (it is :D)\cf3 *\cf2 done \cf3 \
\cf0 \'a0- The variable 'red' is not set globally at Worker/ln53, since the colors\
\'a0\'a0\'a0variable is thread-local (Worker/ln32).\
	- new class Red separate from Colors\
\'a0- The result of post() should be permuted (as stated by Laarman et al.).\
	- email\
\
	- from here: we didn\'92t start on this yet\
\'a0- You do not check whether a state is 'red' (Worker/ln46).\
\'a0- You do not set the color PINK (Worker/ln60).\
\'a0- You do not check whether the state is colored PINK or is 'red'\
\'a0\'a0\'a0(Worker/ln64).\
\'a0- 'await' implemented using a spin lock on a non-volatile variable 'c' (from\
\'a0\'a0\'a0Worker/ln72). \cf2 *now c is volatile \cf0 \
\'a0- Shared variables should be declared volatile in the AtomicCounter class.\
	- 
\f1\fs30 \expnd0\expndtw0\kerning0
make c volatile in AtomicC \cf2 *done
\f0\fs24 \cf0 \expnd0\expndtw0\kerning0
\
\'a0- The Worker class implements NDFS. It is unclear why this is necessary.\
	- not sure, maybe exception issue\
\
Proposed Improvements\
\'a0- Improvement deals with load balancing. No detailed description is provided\
\'a0\'a0\'a0(although the suggested solutions is on a right track).\
	- yay
\fs28 \kerning1\expnd0\expndtw0 \
\pard\tx566\tx1133\tx1700\tx2267\tx2834\tx3401\tx3968\tx4535\tx5102\tx5669\tx6236\tx6803\pardeftab720\pardirnatural
\cf0 \
red: make a class instead of putting it in Colors, since it\'92s global}