KNX BCU ... wie haben die das vor 20 Jahren gemacht?!

[tuxedo]

Hi,

im Rahmen der Entwicklung von KONNEKTING beta5 fällt mir immer wieder auf, dass wir selbst mit heutigen, guten und schnellen Microcontrollern hier und da doch an Limits stoßen, die vor 20 Jahren auch schon galten, aber so "moderne Controller" noch nicht präsent waren...

Ein Beispiel:

Laut https://www.auto.tuwien.ac.at/~mkoeg...dex.php/bcusdk kann so eine BCU 85 KOs, 127 GA und 255 Verknüpfungen zwischen GA<->KO haben.


Wenn nun ein Telegramm eingeht, muss man schauen welche GA es anspricht. Klar. Und dann muss man schauen ob das Telegramm für einen bestimmt ist. Auch klar.
Dazu gibt es im Speicher der BCU "Tabellen" für die Adresse, die Verknüpfungen und die KOs.

Wenn jetzt also so ein Telegramm eingeht, dann muss ich im Worst-Case die GA mit bis zu 127 gespeicherten GAs vergleichen. Eine GA ist 2 byte groß.
Bei 127 GAs sind das schon 254 bytes.

Habe ich dann die GA gefunden, muss ich noch schauen welches KO damit verknüpft ist. Also muss ich im worst-case bis zu 255 Verknüpfungseinträge lesen. Das sind dann nochmal 255 bytes. Und pro gefundener Verknüpfung, muss ich dann noch die Nummer des KO lesen. Da es bis zu 85 KOs geben kann, ist eine GA im worst-case mit 85 KOs verknüpft. Also nochmal 85 bytes.

Macht zusammen 594 bytes.

Wenn man jetzt so schau was "damals" für eine Controller-Familie genutzt wurde (wenn ich richtig recherchiert haben dann ist das sowas: http://de.farnell.com/nxp/mc68hc705c...c44/dp/1661748) , dann können die 594 bytes unmöglich im RAM vorliegen, sondern müssten in einem EEPROM liegen.

Das alles im EEPROM nachzuschlagen kostet doch auch Zeit. Und nebenher muss ich ja schauen, dass ich weitere Telegramme die da eingehen können, vor lauter "im EEPROM suchen" nicht verpasse. Wenn auf dem Bus nix los ist..prima. Aber da kann ja auch mal die Hölle los sein...

Hat da jemand einen etwas tieferen Einblick und kann da ein bisschen darüber plaudern wie das alles gehen soll? Logo, ich bin nicht der Embedded/Microcontroller Experte, un die "echten Freaks" hauen da nochmal einiges an Performance raus wenn sie direkt in Assembler basteln. Aber das sind dennoch Dimensionen wo ich mir überlege: Wow, so ein Worst-Case-Szenario kann doch gar nicht funktionieren?!

[Uwe!]

also ich hab da noch viel weniger Ahnung, aber hast Du da nicht ein Beispiel konstruiert, dass so gar nicht auftreten kann? Die 85 KOs, 127 GA und 255 Verknüpfungen sind ja absolute Obergerenzen, also die kann man ja nicht ausmultiplizieren. Wenn z. B. tatsächlich alle 127 GA genutzt werden, dann können ja max. 126 jeweils eine einzige Verknüpfung und die 127te dann die restlichen 129 Verknüpfungen haben, oder?

Außerdem kann man sowas ja sortiert ablegen, so dass man nicht sequentiell von vorne nach hinten alles abklappern muss.

[tuxedo]

Okay, Sortierung ist eine Möglichkeit dem vielen "lesen" vorzubeugen. Damit kommt man schneller an die passende GA in der GA-Tabelle.

Auch die Verknüpfungstabelle kann man nach GA-ID sortieren. Auch das reduziert. Bleiben dann auf jeden Fall noch die fixen 85 bytes für die max. 85 zugeordneten KOs im Worst-Case.

Müsste mal ausrechnen um wieviel Bytes-Lesen die Sortierung die Situation verbessert.

[update]
Für die (binäre) Suche der GA in der voll ausgefüllten, sortierten Liste, müsste man 14 bytes lesen (worst-case).

Das ist schon mal nicht schlecht.

Die Verknüpfungsliste sieht das ganze anders aus. Da hilft das sortieren wohl meistens, bzw. mach das durchgehen "einfacher" (bedenke: es kann mehrmals eine GA auf unterschiedlice KOs verknüpft sein, d.h. es gibt im Worst-Case 85 Suchergebnisse), aber nicht wirklich besser.

Wenn ich sortiere, dann kommen tauchen gleiche GA-IDs direkt nacheinander auf. Ich muss das "erste" oder "letzte" Auftreten finden. Und dann in die jeweilige Richtung lesen bis ich alle hab. Muss mir mal gedanken machen wieviele lesevorgänge das im Worst-Case sind. Aber definitiv: max 85 bytes für 85 verknüpfungen und zusätzlich noch max. 85 bytes für die ID des zugehörigen KOs. Macht mind. 170 bytes + die Leseversuche die es benötigt um die GAs in der Liste überhaupt zu finden. Wenn das ähnlich effizient geht wie das Suchen in der GA-Liste, dann sind das sicher nicht mehr wie 30 bytes, womit wir bei 200 wären. Zusammen mit den 7 aus der GA Liste, sind es 207.

594 vs. 207 ... wäre schon nicht schlecht. Aber noch mit potential von einigen Bytes "nach unten".

Das Verbessert die Situation schon um Faktor 3.

Danke für diesen Denkanstoß Uwe!

Das hilft u.a. beim entwickeln an KONNEKTING.

[l0wside]

So ganz klar ist mir das Problem noch nicht. Die Vergleichsschleife besteht je Durchlauf aus 1) Zähler erhöhen, 2) Zähler vergleichen, 3) Conditional jump, 4) Pointer erhöhen, 5) Pointer dereferenzieren (kopieren von Speicher in Register), 6) GA vergleichen, 7) Conditional jump. Bei 16 MHz und 1 instruction/cycle sind das 112µs für 256 Werte, etwas mehr als ein Zeichen eines Frames. Selbst wenn die Frames ununterbrochen aufeinanderfolgen, kannst du locker die Auswertung machen, während der nächste Frame im Interrupt empfangen wird. Mit ein bisschen Optimierung (rückwärts statt vorwärts durchsuchen, direkt den Pointer statt eines separaten Zählers vergleichen) geht es noch eine Ecke fixer.
Oder machst du das Empfangen nicht im Interrupt, sondern im Main Loop? Dann natürlich kann es ein Problem werden.

Max

[tuxedo]

Mit Arduino bastelt man für gewöhnlich nicht sooo low-level. Und je mehr High-Level, desto mehr CPU Zyklen :-(
och schwieriger wird es, wenn die Daten aus einem externen (I2C zB) EEPROM kommen.

Unsere bisherige "KNX Stack Struktur" arbeitet nicht mit Interrupts :-( sondern setzt darauf, dass in der main() bzw. loop() immer wieder geschaut wird ob Daten anliegen.
Ist nicht auf meinem Mist gewachsen und langfristig will ich das auch ändern. Aber das wird sicher eine größere Umbaumaßnahme.