Sie sind nicht angemeldet.

  • Anmelden

myabba|abra

Erleuchteter

  • »myabba|abra« ist der Autor dieses Themas

Beiträge: 4 305

Wohnort: Regensburg

Beruf: GER

  • Nachricht senden

1

30.08.2010, 22:12

Abschätzung der Laufzeit

Hallo,
ich muss einen Algorithmus auf dessen Laufzeit bzw. genauer gesagt auf seine Echtzeitfähigkeit auf einer bestimmten Plattform untersuchen.
Details dazu hab ich leider selbst noch nicht zur Hand, bzw. nur sehr grob

Hat von den Informatikern vielleicht dazu eine Literaturempfehlung? Links gehen auch, aber sollte was vernünftig zitierbares sein.

2

31.08.2010, 07:48

Ich habe dann gleich auch noch eine ähnliche Frage:

Ich soll eine Maschine bauen. Hat einer von den Ingenieuren eine Ahnung?

3

31.08.2010, 09:18


myabba|abra

Erleuchteter

  • »myabba|abra« ist der Autor dieses Themas

Beiträge: 4 305

Wohnort: Regensburg

Beruf: GER

  • Nachricht senden

4

31.08.2010, 11:44

Zitat

Original von plizzz
Ich habe dann gleich auch noch eine ähnliche Frage:

Ich soll eine Maschine bauen. Hat einer von den Ingenieuren eine Ahnung?


Versteh ich nicht. Eine ähnliche Frage wäre "Ich soll eine Schaltung designen. Hat da wer ein Buch dazu?" - Da könnt ich dir 5 Bücher aus dem Stand sagen. Natürlich mit unterschiedlichen Schwerpunkten...

Aber wenns konkreter sein soll:

ARM Cortex-A8 Plattform, Bilddatenbearbeitung bei hoher Auflösung, genauer gesagt sollen Bildpunkte "umsortiert" werden, z.B. jede zweite Zeile umdrehen (einfachster Fall).

Aber vll. gehn wir mal von einem einfacheren Fall aus:
Gegeben: Eine C-Implementierung eines Bubblesort-Algorithmus, ein Microcontroller mit 16MHz, der nichts anderes zu tun hat als diese Aufgabe.
Wie würdet ihr da ran gehen?
Ich hab nur die Idee, mir den erstellen Assembler-Code dazu anzusehen und daraus eine Abschätzung zu erstellen. z.B. ADD laut Datenblatt X ns, MPY YY ns

5

31.08.2010, 13:14

Kannst du es nicht austesten, d.h. den Algorithmus auf Testinstanzen laufen lassen und so die Laufzeiten mittracken?

myabba|abra

Erleuchteter

  • »myabba|abra« ist der Autor dieses Themas

Beiträge: 4 305

Wohnort: Regensburg

Beruf: GER

  • Nachricht senden

6

31.08.2010, 13:25

Im Moment leider nicht. Der Algorithmus wird noch entwickelt bzw. liegt mir noch nicht vor. Der wird mir hoffentlich in den nächsten Wochen von extern vorgelegt.

Dass ich im Moment nichts konkretes aussagen kann ist ja klar, ich wollt mich nur schonmal schlau machen damit ich später gleich losstarten kann.

Falls es wen interessiert: Ich hab vor kurzem mit der Diplomarbeit angefangen und bin im Moment etwas auf mich allein gestellt, da in der Firma nicht allzuviel Know-How im Software-Entwurf vorhanden ist und mein Betreuungs-Prof scheinbar im Urlaub ist.

7

31.08.2010, 13:29

Die Bubblesort-Operationen sind doch bekannt, kannst du nicht versuchen rauszubekommen, welche Basisoperationen der Controller (wie schnell?!) verarbeitet und es so abschätzen?

myabba|abra

Erleuchteter

  • »myabba|abra« ist der Autor dieses Themas

Beiträge: 4 305

Wohnort: Regensburg

Beruf: GER

  • Nachricht senden

8

31.08.2010, 14:03

doch, diese Daten hab ich mir schon besorgt.

Interessant wirds halt, wenn im Hintergrund noch Windows Mobile und eine Video dekodierung läuft.

9

31.08.2010, 16:16

Das wirkt irgendwie nicht durchdacht.

Was haben Echtzeit-Betriebssysteme damit zu tun? Um was gehts überhaupt? Um die Laufzeitkomplexität (also O-Notation) oder die konkrete Ausführungszeit auf einer bestimmten Hardware mit einem bestimmten Betriebssystem?

myabba|abra

Erleuchteter

  • »myabba|abra« ist der Autor dieses Themas

Beiträge: 4 305

Wohnort: Regensburg

Beruf: GER

  • Nachricht senden

10

31.08.2010, 16:28

Zitat

Original von MaxPower
die konkrete Ausführungszeit auf einer bestimmten Hardware mit einem bestimmten Betriebssystem?


Genau darum gehts.
"Echtzeit" heißt in diesem Fall, dass die komplette Berechnung in einer bestimmten Zeit durchführbar ist. Da es sich um bewegte Bilder handelt (bzw. handeln kann) also in (1/30Hz) oder (1/60Hz).