Seite 1 von 6

Entgeltliche Optimierung eines Agent-based models

Verfasst: Di Nov 06, 2018 11:13 am
von Anti
Hallo zusammen,

im Rahmen meiner Diss untersuche ich die Besiedelungsgeschichte Polynesiens. Um mögliche Szenarien gegeneinander abzuwägen, habe ich in R ein agenten-basiertes Modell (ABM) erstellt, welches für 242 geographische Gruppen mit max. 120 x 1.0003^t Individuen über einen Zeitraum von 4500 Jahren Migrationen zwischen den Populationen (diese werden als "Deme" bezeichnet, Singular "Dem" - Referenz für Flow Chart) simuliert.

Das Ganze funktioniert bisher, auch wenn das Modell noch nicht vollständig ist (Flow Chart ist angehängt). Bislang habe ich lediglich den Tod der Individuen sowie die Migration zwischen den Populationen implementiert. Allerdings benötigt die Simulation im ersten Jahr (in dem noch nicht mal alle möglichen Populationen existieren - sie werden erst später mit dem Einsetzen von 14C-Datierungen besiedelt) für einen Durchgang (1 Jahr) etwa 30 Minuten.

Ich möchte daher nachfragen, ob mir Jemand von Euch dabei behilflich sein könnte, die Performanz meines Modells zu steigern (Vektorisierung, Ersetzen von Data Frames durch data.tables, Parallelisierung, etc.). Der Code selbst ist nicht sonderlich groß, das ABM umfaßt aktuell (noch unfertig) gerade < 100 Zeilen. Gerne bezahle ich dafür auch einen Obolus. Sofern Interesse besteht, schreibt mir bitte hier oder eine pm mit Eurer Mailadresse.

Vielen Dank im Voraus!
Anti

Re: Entgeltliche Optimierung eines Agent-based models

Verfasst: Di Nov 06, 2018 12:50 pm
von bigben
Hallo Anti,

vorneweg: Ich bin der falsche, andere hier können das mit dem Beschleunigen viel besser. Ich wollte aber gerne schreiben, dass ich mich freue, dass und wie Du die Arbeit dargestellt hast. Das klingt auch für den fachfremden sehr interessant. Erzählst Du uns noch, was Autosomen sind? Die kannte ich bislang nur aus der Genetik.

Zwei Tipps vielleicht vorab, fallst Du nicht sofort jemanden findest:
1. Ich könnte mir vorstellen, dass Du im Laufe Deines Ablaufs sehr viele Zufallsentscheidungen und Zufallszahlen generierst. Hier kann man viel Zeit sparen, wenn man viele Zufallszahlen gleichzeitig und nicht nacheinander abfragt. Vergleiche mal folgende Kommandos:

Code: Alles auswählen

for(i in 1:1e7) rnorm(1)
rnorm(1e7)
Dafür brauchst Du keine Stoppuhr, das fühlst Du auch so.
2. Kommen in Deinem Code viele for-Schleifen vor? Die willst Du wahrscheinlich durch Vektorisierung los werden. Bedenke, dass sich for-Schleifen oft durch foreach-Schleifen aus dem foreach Package ersetzen lassen und dass sie damit sehr leicht zu parallelisieren sind.

Wenn Du brauchbare Ansprechpartner gefunden hast würde ich Deinen Thread danach gerne für eine Interne Diskussion kapern, ob R für soetwas die richtige Sprache ist, oder ob man das nicht gleich in Julia angehen sollte. Steile These, denn die, die ich anspreche, können das auch in R schnell. Aber würde die Schnelligkeit mit einer compilierten Sprache wie C++ oder Julia nicht viel einfacher kommen, viel weniger Hirnschmalz kosten?

Dir erstmal viel Glück,
Bernhard

Re: Entgeltliche Optimierung eines Agent-based models

Verfasst: Di Nov 06, 2018 4:50 pm
von EDi
Aber würde die Schnelligkeit mit einer compilierten Sprache wie C++ oder Julia nicht viel einfacher kommen, viel weniger Hirnschmalz kosten?
Also schneller als netlogo ist R allemal.
Es kommt aber stark drauf an wie man das ibm implementiert. Dazu gibt auch einpaar Beispiele im Netz.

Wenn es nicht zu komplex ist, würde ich in R prototypisieren und dann auf rcpp portieren wenn zu lahm (und der R Code schon optimiert ist).

Oder einfach die Rechenleistung beim cloud-Provider mieten und mir die Kosten fürs refactoring dort investieren.

Re: Entgeltliche Optimierung eines Agent-based models

Verfasst: Di Nov 06, 2018 6:03 pm
von Anti
Hi,

vielen lieben Dank für die Antworten und sorry für die späte Rückantwort - war eben ziemlich busy. Natürlich habe ich schon mein Bestes mit dem Vektorisieren getan, muß aber klar zugeben, daß ich hier an meine Grenzen stoße (wegen fehlender Erfahrung mit ABMs). Mein Prototyp geht halt zunächst durch alle möglichen Individuenalter durch und sampled dann zufällig Individuen, die sterben. Da die Migrationswahrscheinlichkeit sowohl von der Migrationshäufigkeit und max. Migrationsweite der Papuaner, der Migrationshäufigkeit der Austronesier, von der Vernetzung (erzeugt mittles Delaunay-Triangulaten) und den Migrationsdistanzen der zum Zeitpunkt t besiedelbaren Deme ausgeht, habe ich hier relativ viele if-Bedingungen und iteriere durch alle Deme durch. Und mit Autosomen sind auch die Autosomen aus der Genetik, also (Gene auf den) Nicht-Geschlechtschromosomen gemeint.

RCPP wäre natürlich auch eine brauchbare Lösung - allerdings habe ich damit bislang noch nicht gearbeitet.

Wenn Ihr noch mehr wissen wollt oder weitere Anregungen habt, bin ich jederzeit offen. Natürlich können Lösungen dann hier auch als exemplarische Fälle zur Diskussion dienen.

Re: Entgeltliche Optimierung eines Agent-based models

Verfasst: Di Nov 06, 2018 8:53 pm
von Anti
Anbei nun mein bisher geschriebener R-Code sowie die benötigten Dateien.
  • "admixture rates" enthält geschätzte "Verwandtschafts"-Koeffizienten, die am Ende der 4500 simulierten Zeitschritte mit dem Modell-Output (für einen gegebenen Parameter-Range verglichen werden sollen
  • "history" enthält Informationen über die Besiedelung einzelner Deme bzw. die Ankunftszeit der austronesischen Migranten
  • "migration" ist eine Liste, die für jede Population (Informationen der i-ten Population werden mit migration[ [ i ] ] erhalten) einen "probability"-Wert enthält, mit dessen Hilfe Migranten auf die aufgelisteten Populationen aufgeteilt werden, und eine "normalized distance", welche dazu genutzt wird um Migrationen über lange Wegstrecken für überwiegend papuanische Individuen zu unterbinden (vgl. R-Code "slow boat.R").

Re: Entgeltliche Optimierung eines Agent-based models

Verfasst: Mi Nov 07, 2018 9:13 am
von bigben
EDi hat geschrieben: Di Nov 06, 2018 4:50 pmOder einfach die Rechenleistung beim cloud-Provider mieten und mir die Kosten fürs refactoring dort investieren.
Hallo EDi,

grundsätzlich ein guter Gedanke, aber mal überschlagsweise: Das Modell ist noch nicht fertig, braucht aber 30 Minuten pro Jahr. Simuliert werden sollen 4500 Jahre, also braucht das unfertige Modell schon 94 Tage. Man will ja wahrscheinlich n > 1 mal das Modell laufen lassen und auch wenn ich nicht weiß, welche Beschleunigung man von schnellerer Hardware erwarten darf, würde ich auch erst Versuchen, einen guter R'ler mit der Beschleunigung zu beschäftigen oder eine complilierte Sprache ins Auge zu fassen, bevor ich das mit Rechenpower zu erschlagen versuche. Als compilierte Sprache bevorzugt eine, die Parallelisierung leicht macht. Mit Blick auf letzteres weiß ich nicht, ob C++ da die optimale Wahl ist.

LG,
Bernhard


PS: Ok, ich gebe zu, dass ich auch das Geld lieber bei bei Student oder bei consuli sehen würde, als bei Amazon und Co.

Re: Entgeltliche Optimierung eines Agent-based models

Verfasst: Mi Nov 07, 2018 9:27 am
von jogo
Hallo Anti,
Anti hat geschrieben: Di Nov 06, 2018 6:03 pm Wenn Ihr noch mehr wissen wollt oder weitere Anregungen habt, bin ich jederzeit offen. Natürlich können Lösungen dann hier auch als exemplarische Fälle zur Diskussion dienen.
ich habe mir das Skript angesehen und habe meine Schwierigkeiten, es zu lesen. Das liegt u.a. an folgenden Eigenheiten:
  • Du verwendest Matrizen auch dort, wo es sich eigentlich um Dataframes handelt.
  • Du verwendest zum Zugriff auf die Spalte stets die Nummer und nicht den Spaltennamen (wenn Du das so machst, bräuchtest Du keine Namen für die Spalten).
  • Auch die Zeilenbereich werden an jeder Stelle im Code fest kodiert; Beispiel: sehr häufig taucht die Zahl 21000 auf. Warum steht nicht am Anfang des Skripts anzahlIrgendwas <- 21000 ?
  • einige Daten liegen getrennt, obwohl sie zusammen gehören, z.B. death.rate und birth.rate in Abhängigkeit vom Alter.
  • Es gibt zwei verschiedene Objekte death.rate: erst eine Matrix, dann einen Vektor.
Der Umfang des Quelltextes ist schon so groß, dass ich es mir nicht recht zutraue, die Datenstrukturen in eine bequeme Form abzuändern.
Hier aber ein Beispiel dafür, wie ich denersten Teil schreiben würde:

Code: Alles auswählen

#death rates #birth rate
#(from Pietrusewsky, M, Douglas, MT, & Ikehara-Quebral, RM (1997) An Assessment of Health and Disease in the Prehistoric Inhabitants of the Mariana Islands. Am. J. Phys. Anthropol. 104: 315 - 342.)
BD <- data.frame(age=0:55, 
        death_rate=c(0.02, 0.035, 0.0476, 0.07, 0.09, 0.1, 0.1032, 0.1032, 0.093, 0.072, 0.05, 0.047, 0.046, 0.0443, 0.048, 0.055, 0.062, 0.064, 0.0648, 0.073, 0.08, 0.09, 0.093, 0.098, 0.123, 0.145, 0.167, 0.18, 0.1965, 0.198, 0.1995, 0.201, 0.202, 0.2036, 0.23, 0.25, 0.268, 0.27, 0.2757, 0.278, 0.28, 0.283, 0.285, 0.286, 0.29, 0.31, 0.37, 0.42, 0.5, 0.62, 0.73, 0.84, 0.89, 0.94, 0.97, 1),
        birth.rate=c(0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0.001, 0.003, 0.01, 0.04, 0.09, 0.13, 0.17, 0.24, 0.27, 0.29, 0.31, 0.31, 0.295, 0.28, 0.265, 0.245, 0.225, 0.205, 0.19, 0.17, 0.15, 0.13, 0.11, 0.09, 0.075, 0.06, 0.045, 0.03, 0.01, 0.007, 0.0055, 0.0035, 0.0025, 0.0024, 0.0022, 0.0015, 0.001, 0.0005, 0.0001, 0, 0, 0, 0, 0)
)
BD$survival   <- with(BD, { s <- cumsum(death_rate); s <- max(s)-s; s <- s/sum(s); c(s[1:55], NA)})
BD$death.rate <- c(0, -diff(BD$survival/BD$survival[1]), 1)
Der nächste Teil sähe so aus:

Code: Alles auswählen

PopulParam <- list(
  asian.fecundities   = c(3, 4, 5, 6, 7),
  papuan.fecundities  = c(3, 4, 5, 6, 7),
  asian.migrations    = c(0.1, 0.2, 0.3, 0.4, 0.5, 0.6, 0.7, 0.8),
  papuan.migrations   = c(0.1, 0.2, 0.3, 0.4, 0.5, 0.6, 0.7, 0.8),
  marriage.weights    = c(0.00, 0.05, 0.10, 0.15, 0.20, 0.25),
  migration.distances = c(0.2, 0.4, 0.6, 0.8, 1.0)
)
runsummary <- expand.grid(PopulParam)
runsummary <- runsummary[rep(1:nrow(runsummary), 100),]
runsummary <- data.frame(runID=1:nrow(runsummary), runsummary, Aauto=NA, Amt=NA, AY=NA)
Der Teil mit der Migration könnte so aussehen:

Code: Alles auswählen

#migration
Subset <- subset(runlist, (t-BirthYear > 11) & is.na(DeathYear) & is.na(partner) & BirthPlace==residence)
Subset <- Sample[sample.int(nrow(Subset)),]
Gruß, Jörg

Re: Entgeltliche Optimierung eines Agent-based models

Verfasst: Mi Nov 07, 2018 10:15 am
von Anti
jogo hat geschrieben: Mi Nov 07, 2018 9:27 amich habe mir das Skript angesehen und habe meine Schwierigkeiten, es zu lesen. Das liegt u.a. an folgenden Eigenheiten:
Hi jogo,

vielen Dank für Deine Kritik, die ich natürlich gerne annehme. Ich werde versuchen morgen etwas mehr Ordnung in das Chaos zu bringen. Dann werde ich mich wieder melden.

Beste Grüße
Anti

Re: Entgeltliche Optimierung eines Agent-based models

Verfasst: Mi Nov 07, 2018 10:45 am
von jogo
Hallo Anti,

ich habe schon die ersten zwei Teile nach meinem Gusto umgestaltet (siehe vorherige Nachricht).
Ab da wird es etwas komplizierter (weitere Datenobjekte, die umgestylt werden sollten, und Verquickung mit den bisherigen), aber das Prinzip der möglichen Vereinfachungen ist ähnlich.

noch eine Anmerkung:
subset() ist eine R-Funktion, die man sich nicht verbauen sollte, indem man eigene Objekte so nennt.

und noch eine:
Du kannst profitieren von der Technik: Indizieren mit logischem Vektor.

Gruß, Jörg

Re: Entgeltliche Optimierung eines Agent-based models

Verfasst: Mi Nov 07, 2018 4:06 pm
von EDi
bigben hat geschrieben: Mi Nov 07, 2018 9:13 am
EDi hat geschrieben: Di Nov 06, 2018 4:50 pmOder einfach die Rechenleistung beim cloud-Provider mieten und mir die Kosten fürs refactoring dort investieren.
Hallo EDi,

grundsätzlich ein guter Gedanke, aber mal überschlagsweise: Das Modell ist noch nicht fertig, braucht aber 30 Minuten pro Jahr. Simuliert werden sollen 4500 Jahre, also braucht das unfertige Modell schon 94 Tage. Man will ja wahrscheinlich n > 1 mal das Modell laufen lassen und auch wenn ich nicht weiß, welche Beschleunigung man von schnellerer Hardware erwarten darf, würde ich auch erst Versuchen, einen guter R'ler mit der Beschleunigung zu beschäftigen oder eine complilierte Sprache ins Auge zu fassen, bevor ich das mit Rechenpower zu erschlagen versuche. Als compilierte Sprache bevorzugt eine, die Parallelisierung leicht macht. Mit Blick auf letzteres weiß ich nicht, ob C++ da die optimale Wahl ist.

LG,
Bernhard


PS: Ok, ich gebe zu, dass ich auch das Geld lieber bei bei Student oder bei consuli sehen würde, als bei Amazon und Co.
Agree. Meine Rechnung geht auch nur auf, wenn man einfach parallelsieren kann (z. b. mclapply oder furrr drumrum/als schleife), man faul ist und mit miesem code leben kann. Sicherlich eine hässliche Lösung.
Eine Stunde bei einem consultant kostet vermutlich irgendwas um die 150€.
Ein Stunde amazon aws mit 72 Kernen und 140GB RAM kosten irgendwas um die 3 €. Für 150 € kann ich also 50 Stunden rechnen und hat 3600runs durch.

Was auch billig ist (falls man viel Algebra im code hat): das BLAS auf openblas oder intel mkl wechseln. Gibst für lau und die speedups z. b. bei eigenwertzerlegungen sind im 2stelligen prozentbereich. Unter Linux hat man das ruckzuck eingerichtet.