Page 1 of 1

TiS 100

Posted: 23.06.2019, 22:20
by Cybermancer
Wer hilft mir beim parallelisieren des folgenden Problems:

https://pasteboard.co/IkNayWU.jpg

Während mein Instruction Count und die Anzahl benutzter Nodes optimal zu sein scheinen, ist es mein Cycle Count nicht:
https://pasteboard.co/IkNbzgI.jpg

Hat wer Ideen diesen zu optimieren?

Wer wissen will, worum zum Teufel es hier überhaupt geht:

https://www.youtube.com/watch?v=TxJVH5TZQFY

Re: TiS 100

Posted: 24.06.2019, 18:34
by giffi marauder
Cybermancer wrote: 23.06.2019, 22:20 Wer hilft mir beim parallelisieren des folgenden Problems:

https://pasteboard.co/IkNayWU.jpg

Während mein Instruction Count und die Anzahl benutzter Nodes optimal zu sein scheinen, ist es mein Cycle Count nicht:
https://pasteboard.co/IkNbzgI.jpg

Hat wer Ideen diesen zu optimieren?

Wer wissen will, worum zum Teufel es hier überhaupt geht:

https://www.youtube.com/watch?v=TxJVH5TZQFY
Ich bin mir zwar nicht sicher, was der cycle-count so countet,
habe aber die Vermutung, das hat was mit der Gesamtzahl der auugeführten Instruktionen zu tun,
oder ist das der Instruction count, dafür wär der aber zu klein, das ist wohl eher für eine Inputzeile. :gruebel:
Na wie auch immer, das Video ist mir einfach zu lange. :wacko:

Da Prozess(?) 1 und 3 ja mal hautpsächlich nichts tun haben, bzw. drauf warten,
dass Prozess 2 fertig wird (ist das so?), wärs ja eine Idee wenn der 1'er und der 3'er was vom 2'er übernehmen könnten.
Falls ich völlig daneben lieg, kannst jetzt aufhören zu lesen. :-))

Da wäre ganz grob meine Idee IN.S nicht vom 2'er sondern vom 1'er und vom 3'er gleichzeitig auswerten zu lassen
Der 1'er liefert 0 falls IN.S >0 sonst IN.A
Der 3'er liefert 0 bei IN.S <0 sonst IN.B

Der 2'er oder sonst ein x'er zählt "dann" einfach zusammen und gibt das aus.
Oder so ähnlich.
:gruebel:
Den Rest überlass ich dir, weil ich eigentlich keine Idee davon hab was da abgeht,
meine Vermutung ist jedoch dass eine Verminderung des Cycle-Counts dann zulasten des Node-Count geht,
und für alle 3 Werte Minimas gar nicht gleichzeitig erreicht werden können. :-)

Re: TiS 100

Posted: 24.06.2019, 18:59
by Cybermancer
Hast du schon mal von den Connection Machines gehört ?

Das Spiel hat eine davon inspirierte Architektur. Ich dachte eigentlich, den ein oder anderen könnte das interessieren.

Naja, Pech, wenn die meisten hier eh aus der Informatik kommen.

Cycle Count ist die Anzahl der verbrauchten Zyklen, wenn in jedem Zyklus ein Befehl abgearbeitet wird.

Das nächste Mal spiele ich dann wieder Killerspiele. :devil: :devil:

Re: TiS 100

Posted: 25.06.2019, 08:42
by giffi marauder
Cybermancer wrote: 24.06.2019, 18:59 Hast du schon mal von den Connection Machines gehört ?
Zu unserer Zeit (Anfang der 990'er des letzten Jahrtausends) hießen bei uns Transputer.
https://de.wikipedia.org/wiki/Transputer
Damit haben wir auf selbstgestrickter 386'er Architektur eine Anwendung für grafische Bildbearbeitung
inkl. "Zauberstab" zum Freistellen von Vordergründen in Echtzeit in Bilddateien mit hoher Auflösung realisiert. ;)
Die Dinger kosteten ein Vermögen. :help:

Aber das Spielchen ist nett. :yes:
Ich bin bei deinem Problem (am Papier) im Schnitt auf 4 Zyklen je Input-Zeile (ohne Vor- und Nachlauf im Beginn und Ende der Liste)
Allerdings mit 7 Nodes und 18 Instructions.

Re: TiS 100

Posted: 25.06.2019, 14:09
by Cybermancer
Da hast du gegenüber meiner Lösung noch ein paar Instruktionen abknapsen können.

Meine Lösung
https://pasteboard.co/Il2Pdrw.jpg
Die Statistik:
https://pasteboard.co/Il2QgFx.jpg

Magst deine Lösung auch präsentieren?

Re: TiS 100

Posted: 25.06.2019, 14:45
by giffi marauder
Cybermancer wrote: 25.06.2019, 14:09 Da hast du gegenüber meiner Lösung noch ein paar Instruktionen abknapsen können.

Meine Lösung
https://pasteboard.co/Il2Pdrw.jpg
Die Statistik:
https://pasteboard.co/Il2QgFx.jpg

Magst deine Lösung auch präsentieren?
Sorry ich hab beim Zählen der Instruktionen wohl die 3 Nodes mit den einzelnen Moves vergessen. :blush:
Also sinds bei mir dann 21.
Ich hoffe das hat dir keinen schlaflosen Vormittag gekostet. :wacko:

Meine Lösung ist grundsätzlich ident mit zwei kleinen Unterschieden
1) im Additionsnode (mitte, mitte)
Du:
ADD LEFT ACC
ADD RIGHT ACC
MV ACC DOWN
MV NIL.ACC

Ich:
MV LEFT ACC
ADD RIGHT
MV ACC DOWN
-> 1 Instruction weniger
-> 1 Cycle weniger im Gesamtlauf ganz am Schluss.
Mitendrin spielts keine Rolle, weil dieser Node eh meist 1 Zyklus auf Input wartet.
Aber vielleicht geht das auch nur bei mir am Zettel. :gruebel:

2) In den Vergleichs-Nodes Links und Rechts oben, hab ich die letzten beiden Zeilen andersrum,
dann wirds noch schneller, da A oder B auch im S<>0 Fall 1 Zyklus "früher" weitergereicht werden.
Praktisch macht das im Gesamtlauf auch wieder genau 1 Zyklus aus und auch nur ganz am Schluss,
wenn das letzte S <> 0 ist, also durchschnitlich in 2 von 3 Fällen.

Also insgesamt -1 Instruktion und -1,66 Zyklen.
Aber Kleinvieh macht auch Mist. :-))

Spannend wäre, ob die beiden Vergleichsnodes links und rechts auch auf 3 OPS reduziert werden könnten.
Dann hätten wir in jedem Node maximal 3 OPS.
Wär eine schöne Lösung: 4 Nodes unter Volldampf eng ineinander verzahnt und 3 faule Wasserträger. :wub:
Ich bin da aber gescheitert. :(

Re: TiS 100

Posted: 25.06.2019, 16:04
by Cybermancer
Wenn du den Wert im Akkumulator runterreichst, dann bleibt der da drin stehen.
Du musst dir die 0 aus /dev/zero ziehen, sonst werden die folgenden Werte einfach draufaddiert.

Re: TiS 100

Posted: 25.06.2019, 16:11
by giffi marauder
Cybermancer wrote: 25.06.2019, 16:04 Wenn du den Wert im Akkumulator runterreichst, dann bleibt der da drin stehen.
Du musst dir die 0 aus /dev/zero ziehen, sonst werden die folgenden Werte einfach draufaddiert.
Ja eh, aber ich starte ja nicht mit ADD LEFT ACC sondern ein MV LEFT ACC.
Da ist es doch dann egal, was vorher drinnen stand, oder? :gruebel:

Re: TiS 100

Posted: 25.06.2019, 16:46
by Cybermancer
Stimmt,ist heute einfach zu warm.

1 Instruction weniger, aber der Cycle Count bleibt bei 204.

Re: TiS 100

Posted: 25.06.2019, 21:05
by Cybermancer
Und die nächste Aufgabe samt meiner Lösung.
https://pasteboard.co/Il5A6og.jpg

Ziehst noch mit giffi?

Re: TiS 100

Posted: 26.06.2019, 10:40
by giffi marauder
Cybermancer wrote: 25.06.2019, 21:05 Und die nächste Aufgabe samt meiner Lösung.
https://pasteboard.co/Il5A6og.jpg

Ziehst noch mit giffi?
Schöne Lösung :-)

Spontangedanke 1:
Die Weitergabe von B ist eigentlich obsolet,
da B aus A + Diff (=acc) berechnet werden kann.
Der Rechnungsnode wäre dann aber komplexer weil A zweimal verwendet wird
also zwischengespeichert werden müsste. BACC, SWAP etc..
->weniger Nodes aber mehr Zyklen

Spontangedanke2:
MIN (A,B) und MAX(A,B) auf 2 Pfaden berechnen und in dieser Reihenfolge ausgeben
um Vergleiche und Jumps zu eliminieren.
S=A+B
D=Abs(A-B)
MIN(A,B) = (S-D)/2
MAX(A,B) = (S+D)/2
Aber Abs() und durch 2 Teilen kann das Ding wohl nicht. ;)

Da du aber schon bei Maximallänge 4 bist wird das aber schwierig,
da eine Optimierung auf Max 3 je Node zielen müßte. :gruebel:

Re: TiS 100

Posted: 26.06.2019, 16:32
by giffi marauder
Cybermancer wrote: 25.06.2019, 16:46 Stimmt,ist heute einfach zu warm.

1 Instruction weniger, aber der Cycle Count bleibt bei 204.
Ja, hast recht.
Deine 4. Instruction ja läuft parallel zum letzen move, bringt also insgesamt nichts.