[java] Threading problemen

[justice strike]

Ik ben op het moment bezig een Iterative deepening a* algoritme te paralleliseren. ansich zou het niet een probleem zijn. Ik heb de code al uit elkaar gesplits voor meerdere threads.

Echter heb ik het gevoel dat de threads sequentieel uitgevoerd worden ipv in parallel. Als ik namelijk de -Xprof erbij haal dan zie ik namelijk dat een thread bijna 99% van zijn tijd in blocked state staat. Verder is de tijd die het sequentiele programma inneemt nagenoeg hetzelfde als de parallele implementatie.

Het programma wordt gedraait op een dual cpu. En de verwachting is dat er een nagenoeg lineare speedup moet zijn.

ik maak X threads aan die ik doormiddel van een ExecutorService in het leven roep Threads in the runnable stijl.

code:

        ExecutorService threadExecutor = Executors.newFixedThreadPool( thread );
        solution = new ThreadTest[thread];
        bag = new bagOfBoards();
        for(int i = 0;i<thread;i++){
                solution[i] = new ThreadTest(bag, lock, barrier, i);
                threadExecutor.execute(solution[i]);
            }

Verder halen ze hun input uit een bag. Dit zou misschien ervoor kunnen zorgen dat alles serieel is maar ik gok niet dat dit het probleem is. Heeft iemand enig idee of ik iets over het hoofd zie of misschien een suggestie hoe zeker kan weten wat het probleem is. Ik tast nu namelijk hartstikke in het duister. Er is vrijwel geen i/o dus er is ook eigenlijk geen reden om niet een goede speedup te verwachten.

[ Voor 6% gewijzigd door justice strike op 02-02-2007 21:50 ]

[Paul]

Waar of wat is je producer? Is dat die new bagOfBoards?

Ik neem aan dat je consumers een lock willen op je bag op het moment dat ze er iets uithalen? Houd je daar de lock te lang (lees: de hele tijd) vast?

[justice strike]

Paul Nieuwkamp schreef op vrijdag 02 februari 2007 @ 22:03:
Waar of wat is je producer? Is dat die new bagOfBoards?

Ik neem aan dat je consumers een lock willen op je bag op het moment dat ze er iets uithalen? Houd je daar de lock te lang (lees: de hele tijd) vast?

er is geen producer. Er wordt vooraf een zooi boards in die bag gegooid. De functie die de board er weer uithaalt is een synchronized functie. Maar ik heb het ook zonder synchronisation geprobeerd en dat helpt ook niet. Iedere keer halen ze een board eruit en wordt er een recursieve berekening erop losgelaten. Waarna de thread de volgende board er weer uithaalt.

verder gebruik ik nog een cyclicbarrier aangezien het om een iterative deepening probleempje gaat dus bij elke bound wachten alle threads totdat iedereen daar aangekomen is, (op het moment dat de bag leeg is). Maar zelfs dan zou je enige speedup moeten verwachten.

Ik gok dat ik ergens de threads gewoon verkeerd heb aangeroepen. Want ook bij een simpel test voorbeeldje (zonder barriers zonder synchronisation etc...) krijg ik geen speedup. Maar ik kan het dus niet zeker weten

[Verwijderd]

zou je alsjeblieft nog wat vager kunnen zijn?

Wat verwacht je dat we uit dat code fragment gaan halen?

[justice strike]

Verwijderd schreef op vrijdag 02 februari 2007 @ 22:19:
zou je alsjeblieft nog wat vager kunnen zijn?

Wat verwacht je dat we uit dat code fragment gaan halen?

ik kan ook alle bestanden hier posten maar ik denk niet dat dat de bedoeling is. Is er misschien iets specifieks wat je erbij zou willen zien?

Verder weet ik ook zelf niet precies waar het probleem zit (dat is het hele probleem)

[ Voor 159% gewijzigd door justice strike op 02-02-2007 22:37 ]

[Verwijderd]

justice strike schreef op vrijdag 02 februari 2007 @ 22:22:
ik kan ook alle bestanden hier posten maar ik denk niet dat dat de bedoeling is. Is er misschien iets specifieks wat je erbij zou willen zien?

Verder weet ik ook zelf niet precies waar het probleem zit (dat is het hele probleem)

Je hebt het idee dat het geheel als een single thread wordt uitgevoerd. Als dat waar is betekent het waarschijnlijk dat je flink aan het synchroniseren bent. Dus interessante fragmenten zijn sync blocks, blocking methods, etc.

[justice strike]

Dit is de thread zoals hij gemaakt wordt.

Java:

    public int solutionsT(Board board, int currentDepth) {
        int temp = 0;
        int result = 0;
        if(board == null){
            return 0;
        }
        if (board.distance() == 0) {
           return 1;
        }
        if (board.distance() > board.bound()) {
            return 0;
        }
        Board[] children = board.makeMoves();
        result = 0;
        
        for (int i = 0; i < children.length; i++) {
            if (children[i] != null) {
                temp = solutionsT(children[i], currentDepth + 1);
                if(temp != 0){
                    result += temp;
                    }
                }
    }
        return result;
    }
 
    public void run() {
    int temp =0;
    int i = 0;

    while(true){
 
        while(bag.size() !=0){
            bag.putSolution(solutionsT(bag.get(),1));
        }
        try{    
        barrier.await();
        }catch(Exception e){}
        }
   }
}

zo wordt hij aangemaakt. (in een andere class)

Java:

public SolutionThread(int numberOfThreads) {
   thread = numberOfThreads;
   bag = new bagOfBoards();
   barrier = new CyclicBarrier(thread+1);
   if(thread > 1){
      ExecutorService threadExecutor = Executors.newFixedThreadPool( thread );
      solution = new ThreadTest[thread];
      bag = new bagOfBoards();
      for(int i = 0;i<thread;i++){
         solution[i] = new ThreadTest(bag, lock, barrier, i);
         threadExecutor.execute(solution[i]);  
         }
    }
}

verder is dit het gedeelte van bagOfBoards waar hij booards opvraagt

Java:

synchronized public Board get() {
            if (size > 0) {
            size--;
            Board result = bag[size];
            return result;
        } else {
         return null;
         }
    }

nadat de bag gevuld is wordt er in de main thread de barrier getripped (die moet wel functioneren anders zou geen van de threads werk verzetten)

kortom de thread is een oneindige loop met een barrier. Eerst wordt de bag gevuld. daarna wordt de barrier getripped. De workers halen de boards uit de bag en gaan erop rekenen. als de bag leeg is zitten ze weer vast in de barrier.

[ Voor 103% gewijzigd door justice strike op 04-02-2007 01:33 ]

[Confusion]

justice strike schreef op vrijdag 02 februari 2007 @ 21:49:
Er is vrijwel geen i/o dus er is ook eigenlijk geen reden om niet een goede speedup te verwachten.

Heb je wel een multiprocessor systeem? Juist als er van (bijvoorbeeld) blocking I/O sprake is, kan parallelliseren voordelen opleveren op een single processor systeem. Als je 1 processor hebt die alleen maar berekeningen hoeft te doen en nooit staat te wachten, dan maakt het veelal niet uit of dat sequentieel gebeurt (en die ene thread 100% processorcapaciteit gebruikt) of parallel (waarbij losse threads samen 100% gebruiken). Als je echt voor een multiprocessor systeem aan het parallelliseren bent; dan wordt het een ander verhaal en dan zou je wel een verbetering van de performance moeten zien, maar als het een single processor systeem is, kan het heel goed zo zijn dat er niets aan de performance verandert wanneer je het algoritme parallelliseert.

edit:
Hmmm, ik ben kleine-paragraaf-blind geloof ik

[ Voor 14% gewijzigd door Confusion op 02-02-2007 22:45 ]

[justice strike]

Confusion schreef op vrijdag 02 februari 2007 @ 22:42:
[...]

Heb je wel een multiprocessor systeem?.

Dat is een hele goede vraag. Het antwoord is ja. Daarom is het een mysterie voor mij waarom er geen speedup is.

justice strike schreef op vrijdag 02 februari 2007 @ 21:49:
Het programma wordt gedraait op een dual cpu. En de verwachting is dat er een nagenoeg lineare speedup moet zijn.

[ Voor 12% gewijzigd door justice strike op 02-02-2007 22:48 ]

[Verwijderd]

Ik haak hier al af:
"barrier = new CyclicBarrier(thread+1);"

Wat is het idee van de "thread + 1" ?

[Paul]

Java:

while(bag.size() !=0)
{
  bag.putSolution(solutionsT(bag.get(),1));
}

is een race conditie
Mijn Java is wat (*kuch*) roestig, maar forceert synchronized dat stukje niet binnden de context van de mainthread?

Java:

public class Buffer
{
  private Mutex lock;
  private Stack boards;

  public Board Get()
  {
    lock.Aquire();
    try
      if (boards.Size = 0)
        return null
      else
        return boards.Pop();
    finally
    {
      lock.Release():
    }
  }

  public Board Put(Board board)
  {
    lock.Aquire();
    try
        boards.Push(board);
    finally
    {
      lock.Release():
    }
  }


}

// in de thread

Board board = buffer.Get();
while (board != null)
{
    buffer.Put(Berekening(board));
    board = buffer.Get();
}

Alles uit mijn hoofd, gaat meer om de concepten, mijn laatste Java was 4 jaar geleden

[justice strike]

Verwijderd schreef op vrijdag 02 februari 2007 @ 22:48:
Ik haak hier al af:
"barrier = new CyclicBarrier(thread+1);"

Wat is het idee van de "thread + 1" ?

je maakt je worker threads (dat is dus thread) en je hebt je main thread (dat is +1)

doe je geen +1 dan houden de workers elkaar de hele tijd bezig want dan tript de barrier op het moment dat de workers klaar zijn. Dat is niet de bedoeling. Eerst moet de main thread de bag gevuld hebben. Daarna kan de cyclic barrier getripped worden. Waarna de workerthreads weer moeten wachten bij de cyclic barrier totdat de bag weer gevuld is.

[ Voor 16% gewijzigd door justice strike op 02-02-2007 22:52 ]

[justice strike]

Paul Nieuwkamp schreef op vrijdag 02 februari 2007 @ 22:50:

Java:

while(bag.size() !=0)
{
  bag.putSolution(solutionsT(bag.get(),1));
}

is een race conditie
Mijn Java is wat (*kuch*) roestig, maar forceert synchronized dat stukje niet binnden de context van de mainthread?

als ik me niet vergis is het neerzetten van synchronized voor een methode genoeg om acces tot die methode tot 1 thread per keer te limiteren

To make a method synchronized, simply add the synchronized keyword to its declaration
....
Synchronized methods enable a simple strategy for preventing thread interference and memory consistency errors: if an object is visible to more than one thread, all reads or writes to that object's variables are done through synchronized methods

Het zou best kunnen zijn dat ik dat verkeerd begrijp. maar dan moet die online manual van sun herschreven worden

[Verwijderd]

justice strike schreef op vrijdag 02 februari 2007 @ 23:01:
Het zou best kunnen zijn dat ik dat verkeerd begrijp. maar dan moet die online manual van sun herschreven worden

Dat eerste
je beschrijft nu simpel gezegd twee acties:
- grootte van de bag opvragen
- item opvragen

Je wilt hier eigenlijk 1 actie van maken. Dus syncen op een methode is niet voldoende...

[justice strike]

Verwijderd schreef op vrijdag 02 februari 2007 @ 23:04:
[...]
Dat eerste
je beschrijft nu simpel gezegd twee acties:
- grootte van de bag opvragen
- item opvragen

Je wilt hier eigenlijk 1 actie van maken. Dus syncen op een methode is niet voldoende...

ah dat bedoel je sorry dat was niet zo snugger.

had het eerst wat anders. bagOfBoards returned altijd wat. als hij leeg is dan returned hij null. De functie checked of het null is. Geen race conditie meer. (of wel... maar dat maakt niets uit aangezien het geen zak uitmaakt wie als eerste iets uit de bag krijgt)

[ Voor 9% gewijzigd door justice strike op 02-02-2007 23:12 ]

[Verwijderd]

Verwijderd schreef op vrijdag 02 februari 2007 @ 23:04:
[...]
Dat eerste
je beschrijft nu simpel gezegd twee acties:
- grootte van de bag opvragen
- item opvragen

Je wilt hier eigenlijk 1 actie van maken. Dus syncen op een methode is niet voldoende...

Zolang de bag niet door een andere thread kan worden gewijzigd is syncen op de method voldoende.
Edit: ok de synck staat dus op putSolution(), dan heb je idd een probleem.

[ Voor 8% gewijzigd door Verwijderd op 02-02-2007 23:15 ]

[justice strike]

Verwijderd schreef op vrijdag 02 februari 2007 @ 23:12:
[...]

Zolang de bag niet door een andere thread kan worden gewijzigd is syncen op de method voldoende.

hij wordt door de main thread pas gewijzigd als de bag weer helemaal leeg is en alle threads bij de cyclic barrier zijn. dus dat moet kloppen.

[Verwijderd]

justice strike schreef op vrijdag 02 februari 2007 @ 23:13:
[...]


hij wordt door de main thread pas gewijzigd als de bag weer helemaal leeg is en alle threads bij de cyclic barrier zijn. dus dat moet kloppen.

Zou eventueel een probleem kunnen geven als de main thread de bag terug vult waneer hij leeg is.

• putSolution() maakt de size 0
• Main thread ziet dat de bag leeg is en vult hem terug
• while gaat verder

Het is moeilijk om dit juist te interpreteren zonder alle code te bekijken maar misschien toch de moeite om eens te kijken of alle modifiers van je bag counter gesynced zijn.

[justice strike]

Als deze code

code:

bag.putSolution(solutionsT(bag.get(),1));

de bag op 0 zet dan doet de mainthread nog steeds niets. Totdat alle threads geconstateerd hebben dat de bag leeg is. Dan is die iteratie afgelopen en loopt het process weer van voor af aan. (eerst fill bag dan thread workers laten werken.)

hmm misschien moet ik met 2 barriers werken. .. ok er zitten 2 barriers in main. 1 na het fillen van de bag. 1 net voor het returnen (zodat het zeker is dat de threads klaar zijn met werken voordat hij het "antwoord" probeert te returnen. nog steeds geen speedup.

[ Voor 29% gewijzigd door justice strike op 02-02-2007 23:39 ]

[Paul]

Moeten echt alle threads klaar zijn voordat je de bag opnieuw kunt vullen, of wil je pas bijvullen als de bag leeg is maar maakt het niet uit hoever de threads zijn?

Waarom trouwens barriers? Kun je de threads niet stoppen (dus geen while(true) maar while (bag != null) ofzo) als je klaar bent en na het vullen weer Execute aanroepen?
Zijn ze dan _nog_ 99% van de tijd blocked dan is er iig iets anders aan de hand dan dat ze op de barrier staan te wachten

[Verwijderd]

justice strike schreef op vrijdag 02 februari 2007 @ 23:31:
Als deze code

code:

bag.putSolution(solutionsT(bag.get(),1));

de bag op 0 zet dan doet de mainthread nog steeds niets. Totdat alle threads geconstateerd hebben dat de bag leeg is. Dan is die iteratie afgelopen en loopt het process weer van voor af aan. (eerst fill bag dan thread workers laten werken.)

hmm misschien moet ik met 2 barriers werken.

Dan zit je safe.
Het is me wel niet helemaal duidelijk wat er in de Board.get() aan de hand is. Is die if/else niet wat te complex en waarom try/catch bij System.err.println("locking")?

[justice strike]

Paul Nieuwkamp schreef op vrijdag 02 februari 2007 @ 23:42:
Moeten echt alle threads klaar zijn voordat je de bag opnieuw kunt vullen, of wil je pas bijvullen als de bag leeg is maar maakt het niet uit hoever de threads zijn?

Waarom trouwens barriers? Kun je de threads niet stoppen (dus geen while(true) maar while (bag != null) ofzo) als je klaar bent en na het vullen weer Execute aanroepen?
Zijn ze dan _nog_ 99% van de tijd blocked dan is er iig iets anders aan de hand dan dat ze op de barrier staan te wachten

het is een iterative deepening probleempje. Bij elke bound is er een sync (weet je niet meer wanneer er antwoorden tevoorschijn zijn gekomen). Deze bound is als de bag leeg is. immers dat is de startconditie. hij gaat alles na in de bag. vind hij niets dan vult hij de bag weer en gaat hij een niveautje dieper.

Aangezien het iterative deepening is. en er toch gewacht moet worden bij elke bound (totdat de threads klaar zijn) leek een barrier mij makkelijker.

Maar zelfs als je bij de barrier blokked. en je er tijd op verliest dan zou je alsnog enige speedup moeten verwachten. Maar zelfs dat zie ik hier niet. Ik verwacht dus niet dat het een sync probleem is maar misschien dat ik de thread gewoon verkeerd aanroep ofzo (en dus als sequentieel aanroep oid)

[justice strike]

Verwijderd schreef op vrijdag 02 februari 2007 @ 23:42:
[...]

Dan zit je safe.
Het is me wel niet helemaal duidelijk wat er in de Board.get() aan de hand is. Is die if/else niet wat te complex en waarom try/catch bij System.err.println("locking")?

er stond eerst een lock mechanisme. dat is er nu niet meer. ik zal dat ook even weghalen. heb het al even aangepast in die post

en wat bedoel je met de if else te complex? hij returned iets en maakt de size een kleiner. of hij returned null. ik zou niet weten hoe dat anders zou moeten.

[ Voor 3% gewijzigd door justice strike op 02-02-2007 23:51 ]

[Verwijderd]

justice strike schreef op vrijdag 02 februari 2007 @ 23:49:
[...]
en wat bedoel je met de if else te complex? hij returned iets en maakt de size een kleiner. of hij returned null. ik zou niet weten hoe dat anders zou moeten.

Complex was misschien niet helemaal juist uitgedrukt. Ik dacht gewoon dat hij wat compacter en leesbaarder kon. Ik zie trouwens dat je hem al wat hebt aangepast.

[justice strike]

ik wil de bestanden wel opsturen ansich. Maar dan zou je hyperthreading en/of smp moeten hebben. Ik kan er metmijn pet niet bij waarom hij gewoon geen speedup vertoont

[Paul]

Ik zou een JVM moeten installeren (niet zo'n ramp ) maar anders heb ik een dual xeon en (ergens dit weekeinde) een dual opteron waar ik het wel op wil testen hoor?

[justice strike]

met hulp van paul zijn we er (met redelijke zekerheid) achter gekomen dat alles hoogstwaarschijnlijk het sequentieel draait. Dit omdat alles op 1 core draait, ipv 2 cores

2 opties

1.of 1 thread blocked en blijft geblokked (om redenen die duister blijven)
2. de threads worden niet goed aangemaakt. het lijkt een thread object te zijn maar draait als een gewoon adres.

ik neig naar het laatste. Aangezien ik totaal niet zou weten waarom een thread zomaar zou blocken (en geblocked zou blijven)

in de history zie je dat er op 1 core maar een grote piek is. Dit is een test resultaatje met 16 threads. dus hij zou enigszins gelijk verdeeld moeten worden.


verder is hij met 1 thread 8,015 bezig en met 2 threads 8,14. niet echt de speedup waar ik naar opzoek was.

[ Voor 23% gewijzigd door justice strike op 03-02-2007 01:42 ]

[Verwijderd]

Dan is het waarschijnlijk vrij simpel: Hetgeen je threaded wilt uitvoeren is daar helemaal niet voor geschikt. Er zitten nagenoeg geen blokkerende zaken in je threads (geen i/o wait etc). Zodoende is de overhead simpelweg groter als je het threaded uitvoert, en tevens moeten alle threads nog eens wachten bij een barriere; de zwakste schakel krikt dus de tijd op.

Ik had al een beetje genuanceerd proberen aan te geven dat ik nogal wat op een aanmerkingen op je code heb, ik zal het iets minder genuanceerd doen: Het is een zooitje

- Excepties inslikken
- info logging op error
- magere naamgeving van instantie variabelen
- ongestructereerd
- tja en alle threading issues die kunnen spelen zijn net even te veel om op te noemen.

Weet je zeker dat je je met threading wilt bezig houden?

[justice strike]

Verwijderd schreef op zaterdag 03 februari 2007 @ 08:28:
Dan is het waarschijnlijk vrij simpel: Hetgeen je threaded wilt uitvoeren is daar helemaal niet voor geschikt.

Hetgeen wat ik threaded wil uitvoeren is zeer goed geschikt voor parallelisatie.

Ik had al een beetje genuanceerd proberen aan te geven dat ik nogal wat op een aanmerkingen op je code heb, ik zal het iets minder genuanceerd doen: Het is een zooitje

- Excepties inslikken
- info logging op error
- magere naamgeving van instantie variabelen
- ongestructereerd
- tja en alle threading issues die kunnen spelen zijn net even te veel om op te noemen.

Weet je zeker dat je je met threading wilt bezig houden?

het is slordig, daarvan ben ik op de hoogte. Maar het verklaard nog steeds niet waarom het threaden niet werkt. Er zijn maar 2 synchronisatie punten. Zelfs als het een sync probleem zou moeten zijn. Dan zou je nog wel wat speedup verwachten.

[ Voor 6% gewijzigd door justice strike op 03-02-2007 10:53 ]

[Verwijderd]

justice strike schreef op zaterdag 03 februari 2007 @ 10:47:
Hetgeen wat ik threaded wil uitvoeren is zeer goed geschikt voor parallelisatie.

De code die je hier hebt geplaats is er in principe helemaal niet geschikt voor. Maar ik heb het idee dat je (logischerwijs) niet alles hier post. Dus zou je even kunnen uitleggen waarom threads hier van pas kunnen komen en waar je dan vooral (los van meerdere procs) snelheidswinst denkt te behalen?

[ Voor 37% gewijzigd door Verwijderd op 03-02-2007 11:10 ]

[justice strike]

Verwijderd schreef op zaterdag 03 februari 2007 @ 11:07:
[...]
De code die je hier hebt geplaats is er in principe helemaal niet geschikt voor. Maar ik heb het idee dat je (logischerwijs) niet alles hier post. Dus zou je even kunnen uitleggen waarom threads hier van pas kunnen komen en waar je dan vooral (los van meerdere procs) snelheidswinst denkt te behalen?

code:

public int solutionsT(Board board, int currentDepth) {
..
Board[] children = board.makeMoves();
        result = 0;
        
        for (int i = 0; i < children.length; i++) {
            if (children[i] != null) {
                temp = solutionsT(children[i], currentDepth + 1);
                if(temp != 0){
                    result += temp;
                    }
                }
..
}

board.makeMoves(); genereert 4 borden. Die in iteraties recursief opgelost moeten worden.

Wat ik heb gedaan is dat ik de bag vantevoren gevuld heb met boards, door gewoon een paar iteraties children op te wekken.

Daarna gaan de workers aan het werk met de borden. Deze kunnen de bovenstaande code in parallel uitvoeren op de borden die in de bag zitten.

[Verwijderd]

justice strike schreef op zaterdag 03 februari 2007 @ 11:15:
Daarna gaan de workers aan het werk met de borden. Deze kunnen de bovenstaande code in parallel uitvoeren op de borden die in de bag zitten.

dat was de vraag niet, de vraag was waar jij denkt dat de multhreaden jouw performance winst gaat opleveren, los van meerdere processoren.

Wat is nu (single threaded) de bottleneck, waar moet 1 enkele thread op wachten?

[justice strike]

Verwijderd schreef op zaterdag 03 februari 2007 @ 15:40:
[...]
dat was de vraag niet, de vraag was waar jij denkt dat de multhreaden jouw performance winst gaat opleveren, los van meerdere processoren.

multithreaden moet er voor zorgen dat de code op meerdere processoren kan draaien. Daar zit de performance winst in.

Wat is nu (single threaded) de bottleneck, waar moet 1 enkele thread op wachten?

uhm... de processor? the thread is de hele tijd aan het rekenen. De thread komt dus processortijd tekort. Dat wil ik met multithreaden versnellen. anders heeft het geen nut om het op een smp systeem te draaien. verder is er geen bottleneck.

De bag is geen bottleneck. immers kost het returnen van een board vrijwel geen tijd vergeleken met het verwerken van de board. de main thread doet op een single processor het vullen van de bag. maar dat is vergeleken met de recursieve berekening ook peanuts als je het vergelijkt met wat de workersthreads meoten doen. De echte peformance winst zit echt in het parallel uitvoeren van de code.

(of ik moet je punt echt helemaal voorbij gaan)

[ Voor 35% gewijzigd door justice strike op 03-02-2007 15:47 ]

[Remus]

Probeer het genereren van de oplossing eens te scheiden van de aanroep van putSolution. Als ik de Java Language Specification goed interpreteer dan wordt bij het aanroepen van een synchronized method eerst de monitor verkregen voordat de methode daadwerkelijk wordt aangeroepen.
Dat zou dus ook kunnen betekenen dat de actuele parameters pas worden geëvalueerd als de lock eenmaal is verkregen, en laat je actuele parameter nou net de methode zijn die de oplossing genereert.

Als mijn vermoeden klopt, dan zou het dus betekenen dat er op ieder moment slechts één thread echt werk verricht.

edit:
Lezen van paragraaf 15.12.4 van de JLS laat zien dat ik ongelijk heb

[ Voor 6% gewijzigd door Remus op 03-02-2007 17:13 ]

[justice strike]

Remus schreef op zaterdag 03 februari 2007 @ 17:07:
Probeer het genereren van de oplossing eens te scheiden van de aanroep van putSolution. Als ik de Java Language Specification goed interpreteer dan wordt bij het aanroepen van een synchronized method eerst de monitor verkregen voordat de methode daadwerkelijk wordt aangeroepen.
Dat zou dus ook kunnen betekenen dat de actuele parameters pas worden geëvalueerd als de lock eenmaal is verkregen, en laat je actuele parameter nou net de methode zijn die de oplossing genereert.

Als mijn vermoeden klopt, dan zou het dus betekenen dat er op ieder moment slechts één thread echt werk verricht.

edit:
Lezen van paragraaf 15.12.4 van de JLS laat zien dat ik ongelijk heb

putSolution is non synchronized. Ik ga eventjes alle bestanden posten of in iedergeval een interfaceje ervan.

[justice strike]

ik zet een linkje hier neer. het wordt wat chaotisch anders.

http://www.calesco.nl/ida-threads14.zip

[ Voor 128% gewijzigd door justice strike op 03-02-2007 17:34 ]

[misfire]

Meten is weten. Heb je al met een profiler gekeken hoe het threading gedrag is van je applicatie, of er ergens duidelijke bottlenecks zijn, of dingen niet stiekem toch multi-threaded worden uitgevoerd, maar gewoon minder dan je denkt? Een alternatief is JConsole. Sinds Java 6 kun je hier echt alle locks mee zien, en de JConsole van Java 6 is ook beter en makkelijker.

[justice strike]

misfire schreef op zaterdag 03 februari 2007 @ 19:08:
Meten is weten. Heb je al met een profiler gekeken hoe het threading gedrag is van je applicatie, of er ergens duidelijke bottlenecks zijn, of dingen niet stiekem toch multi-threaded worden uitgevoerd, maar gewoon minder dan je denkt? Een alternatief is JConsole. Sinds Java 6 kun je hier echt alle locks mee zien, en de JConsole van Java 6 is ook beter en makkelijker.

1 thread blocked voor de meeste tijd en de andere draait. althans dat zegt -Xprof. Er is geen reden voor een thread om te blocken anders dan dat hij moet wachten totdat de proc klaar is. Verder heeft de windows manager aangegeven dat alles op 1 proc draait. ik ga even kijken naar jconsole

[Confusion]

justice strike schreef op vrijdag 02 februari 2007 @ 22:37:
zo wordt hij aangemaakt. (in een andere class)

code:

public SolutionThread(int numberOfThreads) {
   thread = numberOfThreads;
   bag = new bagOfBoards();
   barrier = new CyclicBarrier(thread+1);
   if(thread > 1){
      ExecutorService threadExecutor = Executors.newFixedThreadPool( thread );
      solution = new ThreadTest[thread];
      bag = new bagOfBoards();
      for(int i = 0;i<thread;i++){
         solution[i] = new ThreadTest(bag, lock, barrier, i);
         threadExecutor.execute(solution[i]);  
         }
    }
}

Dit is volgens mij problematisch. Je barrier wacht tot er 'thread+1' parties een await() op de barrier hebben aangeroepen. Maar je maakt 'thread' parties aan in de lus. Er gaan ook maar 'thread' parties in de solution array. De barrier krijgt dus nooit genoeg await() calls?

[justice strike]

Confusion schreef op zaterdag 03 februari 2007 @ 19:31:
[...]

Dit is volgens mij problematisch. Je barrier wacht tot er 'thread+1' parties een await() op de barrier hebben aangeroepen. Maar je maakt 'thread' parties aan in de lus. Er gaan ook maar 'thread' parties in de solution array. De barrier krijgt dus nooit genoeg await() calls?

justice strike schreef op vrijdag 02 februari 2007 @ 22:51:
[...]


je maakt je worker threads (dat is dus thread) en je hebt je main thread (dat is +1)

doe je geen +1 dan houden de workers elkaar de hele tijd bezig want dan tript de barrier op het moment dat de workers klaar zijn. Dat is niet de bedoeling. Eerst moet de main thread de bag gevuld hebben. Daarna kan de cyclic barrier getripped worden. Waarna de workerthreads weer moeten wachten bij de cyclic barrier totdat de bag weer gevuld is.

Maar er is wel een probleem met de barrier zoals ik dat van jconsole kan concluderen (goede tip misfire... ik wou dat ik dat programma een maand eerder had ) Blijkbaar blijft 1 van de worker threads haken bij de barrier. Waarom dat is dat weet ik niet:S aangezien er wel een thread verder gaat met werk. (even de specs opzoeken, maar als de barrier bereikt wordt gaan alle threads door... of ik moet me vergissen en gaat er maar 1tje door de barrier)

[ Voor 16% gewijzigd door justice strike op 03-02-2007 19:44 ]

[Verwijderd]

justice strike schreef op zaterdag 03 februari 2007 @ 15:42:
[...]


multithreaden moet er voor zorgen dat de code op meerdere processoren kan draaien. Daar zit de performance winst in.

[...]

Draai je de code op een echt multi core/cpu systeem of op een P4 met hyperthreading? In dat laatste geval gebruikt 1 thread misschien al alle processor resources en kan de cpu er geen 2e thread tussen weven.

Als je twijfelt of de thread scheduling wel doet wat ze moet doen zou ik dat eens proberen te testen met een simpele dummy job die je over je cores probeert te schedulen.

[justice strike]

Verwijderd schreef op zaterdag 03 februari 2007 @ 19:52:
[...]


Draai je de code op een echt multi core/cpu systeem of op een P4 met hyperthreading? In dat laatste geval gebruikt 1 thread misschien al alle processor resources en kan de cpu er geen 2e thread tussen weven.

yes het wordt op een echte smp gedraait. dual pentium (en paul heeft het geprobeert op zijn dual xeon + hyperthreading)

Als je twijfelt of de thread scheduling wel doet wat ze moet doen zou ik dat eens proberen te testen met een simpele dummy job die je over je cores probeert te schedulen.

dat heb ik geprobeert. Alles wijst erop dat er wel gewoon echt meerdere threads zijn (vm geeft met -Xprof echt meerdere threads aan). Het probleem echter is. dat de threads na elkaar draaien en niet tegelijk., maar ik denk dat er iets met de barrier is. dus ik ga even kijken of dat het probleem kan verhelpen.

/edit Er zit waarschijnlijk een fout in cyclicbarrier class (althans dat lees ik zo hier en daar) heeft iemand een ander ideetje? ik dacht aan checken op idle threads.. maar dat pollen kost zoveel cycles

[ Voor 9% gewijzigd door justice strike op 03-02-2007 20:32 ]

[Confusion]

justice strike schreef op vrijdag 02 februari 2007 @ 22:51:
Eerst moet de main thread de bag gevuld hebben.

In principe is de Runnable die je aan de Barrier mee kan geven bedoeld voor dat soort functionaliteit, maargoed, zo zou het ook moeten werken. Roep je niet per ongeluk de await() in de 'main' thread aan nadat je alles voor de eerste keer gevuld hebt? Want dan wordt de barrier getripped op het moment dat alle worker threads klaar zijn en is er dus geen enkele garantie dat de 'main' thread de eerste is die weer wordt uitgevoerd.

Sowieso begrijp ik niet helemaal hoe je garandeert dat de main thread nieuw werk voor alle workers heeft klaargezet vlak voordat de barrier getripped wordt.

[justice strike]

Confusion schreef op zaterdag 03 februari 2007 @ 20:37:
[...]

In principe is de Runnable die je aan de Barrier mee kan geven bedoeld voor dat soort functionaliteit, maargoed, zo zou het ook moeten werken. Roep je niet per ongeluk de await() in de 'main' thread aan nadat je alles voor de eerste keer gevuld hebt? Want dan wordt de barrier getripped op het moment dat alle worker threads klaar zijn en is er dus geen enkele garantie dat de 'main' thread de eerste is die weer wordt uitgevoerd.

de threads zijn idle op het moment dat de bag gevuld wordt. Dan wordt inderdaad await aangeroepen waardoor de workers aan het werk gaan met die bag. De main thread wacht vervolgens bij de volgende barrier en als de workers klaar zijn trippen ze weer de barrier. op dat moment leest de main thread de gegevens uit.

Het is eigenlijk geen main thread maar een object die een iteratie afhandeld. elke keer doet het object 1 iteratie. Hij vult een bag. dan laat hij de workers het oplossen en retourneert dan het antwoordt. Op een hoger niveau staat een loopje die doorgaat zolang de return value 0 is. maar dat is niet van belang.

het is dus voor de main thread:
fillbag->tripbarrier->waitatnextbarrier->readsolution(->fillbag)

voor de worker thread is het:
waitatbarrier->processbag->putsolution->tripbarrier(->waitatbarrier)

Sowieso begrijp ik niet helemaal hoe je garandeert dat de main thread nieuw werk voor alle workers heeft klaargezet vlak voordat de barrier getripped wordt.

heel simpel. de thread is geen producer. Het is alleen een intialiser. Hij geeft alleen aan het begin een bag met boards die geprocessed moeten worden. Dus als je dat kan garanderen dan weet je dat die bag maar 1 keer gevuld hoeft te worden. (dat er op een hoger niveau iteraties op het geheel worden gedaan is niet van belang)

De main thread roept een object aan die de recursieve oplossing distribueerd over meerdere threads. hij roept per iteratie 1 functie op en controleert of de return value 0 is.

het enige wat het solutionobject doet is de bag vullen en dan de workers daarvan op de hoogte stellen. De bag wordt gedurende die iteratie niet meer gevuld. De workers stellen het solutionobject op de hoogte dat de bag leeg is. Waarna het solutionobject kijkt naar het antwoordt en deze retourneert. naargelang het antwoord wordt er weer een iteratie gedaan.

het is dus geen consumer/producer probleem Immers wordt de bag niet gevuld gedurende het processen.

[ Voor 35% gewijzigd door justice strike op 03-02-2007 20:58 ]

[Confusion]

Ik weet het niet helemaal zeker, want ik kan niet zo snel wegwijs worden in je code, maar ik heb het idee dat je maar 1 bag hebt, waar je meerdere worker threads tegelijk uit laat werken. In de bag zitten echter tegelijkertijd maar een klein aantal Boards, waardoor 1 thread ze misschien allemaal al heeft verwerkt voordat de anderen de kans krijgt er een paar uit te vissen?

Dat nog los van de race condition die Paul N. al noemde en de kans dat meerdere threads tegelijkertijd op hetzelfde Boards object opereren.

[justice strike]

Confusion schreef op zaterdag 03 februari 2007 @ 23:54:
Ik weet het niet helemaal zeker, want ik kan niet zo snel wegwijs worden in je code, maar ik heb het idee dat je maar 1 bag hebt, waar je meerdere worker threads tegelijk uit laat werken. In de bag zitten echter tegelijkertijd maar een klein aantal Boards, waardoor 1 thread ze allemaal al heeft verwerkt voordat de anderen de kans krijgt er een paar uit te vissen.

ansich een goed puntje. Ik heb het al getest met een groot aantal boards in de bag hetzelfde resultaat. Daarbij duurt het erg lang om een board uit te rekenen. de non threading versie doet er namelijk 30 seconden over.

Dat nog los van de race condition die Paul N. al noemde en de kans dat meerdere threads tegelijkertijd op hetzelfde Boards object opereren.

Er is geen race conditie de bag wordt 1 keer gevuld. Dan wordt er alleen maar uitgehaald. De worker threads krijgen altijd iets uit de bag en moeten zelf testen of datgene wat ze krijgen null is. Ik kan me echt niet voorstellen dat daar alles vastloopt.

[Paul]

Dat maakt het niet minder een race conditie Tussen bag.size en bag.Get() kan Size weer veranderd zijn en Get() dus iets ongeldigs opleveren.

Dat je vervolgens op dat ongeldige gaat testen wil niet zeggen dat het geen race conditie is

Java:

synchronized public Board Get()
{
  if (size <= 0)
  {
    return null;
  }
  else
  {
    return bag[--size]; // eerst verlagen, dan size teruggeven
  }
}

public void run()
{
  Board board = bag.Get();
  while board != null)
  {
    int soultion = solutionsT(board, 1);
    bag.PutSollution(solution);
    board = bag.Get();
  }
}

Mag ik overigens opmerken dat je een zooitje maakt van je code standaard? size() ipv getSize() maar weer wel getDepth(), hoofdlettergebruik wisselt nogal eens, de ene keer specificeer je wel de scope de andere keer niet, de uitlijning is een zooi (dan 4 spaties, dan 2, dan helemaal niet).

[justice strike]

in de worker thread wordt er gechecked op een null board

code:

public int solutionsT(Board board, int currentDepth) {
        int temp = 0;
        int result = 0;
        if(board == null){
            return 0;
        }


...
...

p.s. yes, ik gooi meestal mijn code door een beautifier als ik klaar ben.

[ Voor 13% gewijzigd door justice strike op 04-02-2007 00:48 ]

[Soultaker]

Een kosmetisch puntje: als je je code post met [code=java] ... [/code] dan hebben we ook mooie syntax highlighting (en geen last van de dubbele-newline-bug die zich momenteel manifesteert).

Verder werkt A* voor zover ik weet met priority queue waar steeds het voorste element uitgehaald wordt, anders klopt de uitkomst niet. Hoe dacht je dat handig te parallelliseren?

[justice strike]

Soultaker schreef op zondag 04 februari 2007 @ 01:10:
Verder werkt A* voor zover ik weet met priority queue waar steeds het voorste element uitgehaald wordt, anders klopt de uitkomst niet. Hoe dacht je dat handig te parallelliseren?

priority queue? het is een iterative deepening probleem. Wat je wil doen is de boom net genoeg uitklappen dat je nodes genoeg hebt. Dan de nodes verdelen over de threats welke deze dan recursief oplossen.

in dit voorbeelde je de sequentiele oplossing

Java:

do {
        board.setBound(bound);

        if (board.distance() == 0) {
            return 1;
        }
        
        if (board.distance() > board.bound()) {
            return 0;
        }

        Board[] children = board.makeMoves();
        result = 0;
        
        for (int i = 0; i < children.length; i++) {
            if (children[i] != null) {
                temp = solutionsT(children[i]);
                if(temp != 0){
                    result += temp;
                    }
                }
            }
bound += 2;
} while (solutions == 0 );

het is heel makelijk te zien dat je ipv de children iteratief op te lossen je deze in parallel kunt zetten.

ipv

Java:

for (int i = 0; i < children.length; i++) { 
     if (children[i] != null) { 
         temp = solutionsT(children[i]); 
         if(temp != 0){ 
             result += temp; 
             } 
         } 
}

krijg je dus iets in de trant van dit

Java:

for (int i = 0; i < children.length; i++) { 
     if (children[i] != null) { 
         temp = thread[i].execute(solutionsT(children[i]));  
         if(temp != 0){ 
             result += temp; 
             } 
         } 
     }

maar dan moet de code van solutionsT(children[i]) in een object verwerkt worden (of weet iemand een andere manier om een thread een enkele methode uit te laten voeren)

[ Voor 28% gewijzigd door justice strike op 04-02-2007 01:38 ]

[MNeMoNiCS]

Paul Nieuwkamp schreef op zondag 04 februari 2007 @ 00:32:
Dat maakt het niet minder een race conditie Tussen bag.size en bag.Get() kan Size weer veranderd zijn en Get() dus iets ongeldigs opleveren.

Dat je vervolgens op dat ongeldige gaat testen wil niet zeggen dat het geen race conditie is

aangezien deze statements beide in een synchronized methode staan, en aangezien alleen deze methode de bag kan wijzigt (oftewel: alle methoden die wijzigingen aanbrengen zijn synchronized), kan er toch geen probleem optreden?

Mag ik overigens opmerken dat je een zooitje maakt van je code standaard? size() ipv getSize() maar weer wel getDepth(), hoofdlettergebruik wisselt nogal eens, de ene keer specificeer je wel de scope de andere keer niet, de uitlijning is een zooi (dan 4 spaties, dan 2, dan helemaal niet).

Wat is het nut van een dergelijke opmerking in deze context... en trouwens size() is een methode die in veel standaard java classes voorkomt.

[Soultaker]

justice strike schreef op zondag 04 februari 2007 @ 01:31:
priority queue? het is een iterative deepening probleem. Wat je wil doen is de boom net genoeg uitklappen dat je nodes genoeg hebt. Dan de nodes verdelen over de threats welke deze dan recursief oplossen.

Oh ja, die variatie. (Is eigenlijk niet echt A*; je gebruikt alleen eenzelfde heuristische cut-off als met A*.) Dan mis ik in je code nog steeds die cut-off, maar ik berijp wat ongeveer de bedoeling is.

Dat moet zeker goed te parallelliseren zijn, maar de code die je post komt bijzonder rommelig over (en lijkt ook steeds wat anders te zijn). Waar je voor moet zorgen is dat een thread een voldoende grote job heeft om uit te voeren, voordat 'ie weer synchroniseert. Ik vind het nu lastig te zien hoe je precies schedulet; ik zou zelf alle invoer in een queue/bag doen, en alle uitvoer in een andere queue/bag; jij stopt ze in dezelfde, maar dat zorgt alleen maar voor nodeloze contention.

Verder is het bij A* meestal van belang dat je elke toestand slechts één keer bezoekt (voor sommige problemen gaat dit vanzelf goed). Dit is lastig te parallelliseren (en is ook een van de moeilijkste dingen bij het parallelliseren van bijvoorbeeld schaakprogramma's): als je een gedeelde set van bezochte toestanden bijhoudt, moet je die steeds synchroniseren (inefficiënt, en veel contention). Een alternatief is om per thread een lokale set bij te houden, maar het nadeel daarvan is dat verschillende threads best dezelfde toestand kunnen bezoeken, waardoor je niet de lineaire snelheidswinst krijgt die je zou willen. Uit de geposte code kan ik helaas niet opmaken of dat is wat hier gebeurt.

[justice strike]

Soultaker schreef op zondag 04 februari 2007 @ 02:15:
[...]
Dat moet zeker goed te parallelliseren zijn, maar de code die je post komt bijzonder rommelig over (en lijkt ook steeds wat anders te zijn). Waar je voor moet zorgen is dat een thread een voldoende grote job heeft om uit te voeren, voordat 'ie weer synchroniseert.

dat probeer ik te doen door de bag groot genoeg te maken. (192 initial nodes moet genoeg zijn)

Ik vind het nu lastig te zien hoe je precies schedulet; ik zou zelf alle invoer in een queue/bag doen,

dat doe ik

en alle uitvoer in een andere queue/bag; jij stopt ze in dezelfde, maar dat zorgt alleen maar voor nodeloze contention.

er is alleen antwoordt namelijk een int. of ik die nu in dezelfde bag gooi of in een andere moet voor de oplossing niets uitmaken. immers hoef ik alleen te weten hoeveel oplossingen er zijn voor een gegeven diepte. (een enkele int in een bag gooien is trouwens ook niet nuttig.

Verder is het bij A* meestal van belang dat je elke toestand slechts één keer bezoekt (voor sommige problemen gaat dit vanzelf goed). Dit is lastig te parallelliseren (en is ook een van de moeilijkste dingen bij het parallelliseren van bijvoorbeeld schaakprogramma's): als je een gedeelde set van bezochte toestanden bijhoudt, moet je die steeds synchroniseren (inefficiënt, en veel contention). Een alternatief is om per thread een lokale set bij te houden, maar het nadeel daarvan is dat verschillende threads best dezelfde toestand kunnen bezoeken, waardoor je niet de lineaire snelheidswinst krijgt die je zou willen. Uit de geposte code kan ik helaas niet opmaken of dat is wat hier gebeurt.

ik ga voor het laatste. Dat het dus niet uitmaakt dat states meerdere keren worden opgezocht.

[Paul]

MNeMoNiCS schreef op zondag 04 februari 2007 @ 01:54:
aangezien deze statements beide in een synchronized methode staan

ThreadTest.java regel 99

Wat is het nut van een dergelijke opmerking in deze context...

Dat de code lastig te lezen valt, wat het debuggen niet echt ten goede komt.

[MNeMoNiCS]

Paul Nieuwkamp schreef op zondag 04 februari 2007 @ 03:14:
[...]
ThreadTest.java regel 99

Oh in dat geval heb je gelijk, ik heb niet alle code bekeken en veronderstelde dat het ging om het stukje dat je erbij postte. Dat stukje is inderdaad incorrect, maar is het wel een race conditie? Wat mij betreft wordt er alleen een assertie gedaan waarvan de waarheid niet meer gegarandeerd kan worden bij het uitvoeren van de get. In het geval dat het fout gaat levert get gewoon een null board, er zal echter niks blokkeren (waarschijnlijk alleen een nullpointerexception).

[Paul]

MNeMoNiCS schreef op zondag 04 februari 2007 @ 11:45:
Oh in dat geval heb je gelijk, ik heb niet alle code bekeken en veronderstelde dat het ging om het stukje dat je erbij postte.

Dat stukje wat ik erbij poste was mijn rewrite

Wat mij betreft wordt er alleen een assertie gedaan waarvan de waarheid niet meer gegarandeerd kan worden bij het uitvoeren van de get.

Wat is dan jouw definitie van race conditie? Want je beschrijft daar wel de mijne

er zal echter niks blokkeren (waarschijnlijk alleen een nullpointerexception).

En een NPE is geen fout? De normaalste zaak van de wereld?

Goed, er wordt (in doit geval) afgevangen of je een null terugkrijgt (ergens in solutionsT(...)), maar als je dan toch al op null checkt, waarom dan nog de size opvragen?

[justice strike]

Paul Nieuwkamp schreef op zondag 04 februari 2007 @ 13:28:
Goed, er wordt (in doit geval) afgevangen of je een null terugkrijgt (ergens in solutionsT(...)), maar als je dan toch al op null checkt, waarom dan nog de size opvragen?

omdat het misschien een enkele keer fout zal gaan. maar over het algemeen zal dat de meest efficiente manier zijn om te concluderen dat je klaar bent met de loop.

[MNeMoNiCS]

justice strike schreef op zondag 04 februari 2007 @ 15:53:
[...]


omdat het misschien een enkele keer fout zal gaan. maar over het algemeen zal dat de meest efficiente manier zijn om te concluderen dat je klaar bent met de loop.

Ja maar paul heeft wel gelijk dat je nu tweemaal controleert of er een board beschikbaar is: eerst vóór de get door de size of the vragen (en zoals paul opmerkt, dat stukje is niet correct maar zou hier geen probleem mogen veroorzaken) en ten tweede door op null te checken.

[justice strike]

MNeMoNiCS schreef op maandag 05 februari 2007 @ 12:02:
[...]


Ja maar paul heeft wel gelijk dat je nu tweemaal controleert of er een board beschikbaar is: eerst vóór de get door de size of the vragen (en zoals paul opmerkt, dat stukje is niet correct maar zou hier geen probleem mogen veroorzaken) en ten tweede door op null te checken.

aangezien het om een performance parallel programma gaat is dit kwa peformance het beste (zonder problemen te krijgen met racing conditions)

[Verwijderd]

justice strike schreef op dinsdag 06 februari 2007 @ 13:27:
aangezien het om een performance parallel programma gaat is dit kwa peformance het beste (zonder problemen te krijgen met racing conditions)

Misschien is het een tip om je eerst eens te richten op de correctheid van je programma. Er staan nu gewoon teveel fouten in. Als de snelheid daarna nog tegen valt, dan pak je dat op.