DE10128752A1 - Verfahren zur Ablage von Daten in einen Speicherbaustein - Google Patents

Abstract

Es wird ein Verfahren zur Ablage von Daten in einen Speicherbaustein (30) beschrieben. Dieser Speicherbaustein (30) ist in mehrere unabhängig voneinander zu programmierende Speichereinheiten (35) aufgeteilt. DOLLAR A Bei dem Verfahren werden eine Anzahl von veränderlichen Werten in verketteten Listen abgelegt. DOLLAR A Das Verfahren zeichnet sich dadurch aus, daß beim Abspeichern einer Instanz in eine erste Speichereinheit (35) gleichzeitig eine zweite Speichereinheit (35) belegt wird und in die erste Speichereinheit (35) die Instanz und der Verweis auf die zweite Speichereinheit (35) abgelegt werden.

Description

Die Erfindung betrifft ein Verfahren zur Ablage von Daten in einen Speicherbaustein. Insbesondere betrifft die Erfindung ein Verfahren, welches eine möglichst flexible Datenablage für verkettete Listen in Speicherbausteinen, welche nicht auf Byte- oder Wortebene lösch- oder programmierbar sind, ermöglicht.

Stand der Technik

EEPROMs sind Halbleiterspeicher, welche die in ihnen gespeicherten Werte im Gegensatz zu RAM-Bausteinen auch ohne Versorgungsspannung beibehalten. EEPROMs werden oft statt mit einem parallelen Businterface durch ein serielles Businterface, wie z. B. I²C oder SPI, angesteuert und sind in Größen von einigen Bytes bis wenigen Kilobytes verfügbar.

Lese- und Schreibvorgänge sind bei EEPROMs ähnlich wie bei RAM-Bausteinen möglich, wobei im Unterschied zu letzteren schreibende Zugriffe eine deutlich längere Zeit in Anspruch nehmen als lesende Zugriffe. Außerdem müssen bei EEPROMs vor dem Ändern des Inhalts von Speicherzellen, im Gegensatz zu EPROMs, diese nicht gelöscht werden.

EEPROMs sind oft in sogenannte Pages aufgeteilt, die typischerweise 16 oder 32 Bytes groß sind. Diese Page- Struktur hat für lesende Zugriffe keine Bedeutung, jedoch kann das gegenüber dem Schreiben auf einzelne Speicherzellen (Byte Writes) schnellere sequentielle Schreiben auf aufeinanderfolgende Adressen (Page Writes) nur innerhalb einer einzigen Page geschehen. Deshalb sind die in EEPROMs zu speichernden Daten ebenfalls oft in Pages organisiert.

Flashbausteine sind Halbleiterspeicher, die, genauso wie EPROMs oder auch EEPROMs, die in ihnen gespeicherten Werte auch ohne Versorgungsspannung beibehalten. Üblicherweise werden sie über ein paralleles Businterface angesteuert.

Lesezugriffe werden bei Flashbausteinen, ebenso wie bei RAM-Bausteinen oder normalen ROM-Bausteinen, durchgeführt. Im Gegensatz zu RAM-Bausteinen oder EEPROMs können Flashbausteine jedoch nicht byte- oder wortweise wiederholt beschrieben werden. Vor jedem Schreibzugriff muß der vorherige Inhalt einer Speicherzelle gelöscht werden, da Schreibzugriffe einzelne Bits nur in einer Richtung, z. B. von 1 nach 0, umprogrammieren können.

Auch bei Flashbausteinen nehmen Schreibzugriffe eine deutlich längere Zeit in Anspruch als lesende Zugriffe.

Das Löschen von Flashbausteinen wird, ebenso wie Schreibvorgänge, durch Softwarekommandos ausgelöst. Es kann jedoch nicht byte- oder wortweise erfolgen, sondern nur für komplette Sektoren auf einmal. Typische Sektorgrößen bewegen sich im Bereich von wenigen bis einigen zehn Kilobytes.

Im Gegensatz zu den Pages bei EEPROMs sind die einzelnen Sektoren eines Flashbausteins nicht gleich groß. Das Löschen eines Sektors benötigt Zeiten im Sekundenbereich. Ebenso wie bei Schreibvorgängen können während des Löschens keine lesenden Zugriffe auf Speicherzellen desselben Bausteins durchgeführt werden. Viele Flashtypen bieten jedoch die Möglichkeit, das Löschen für Lese- oder gar Schreibzugriffe auf andere Sektoren per Kommando zu unterbrechen und später wieder aufzunehmen.

Aus der DE 42 23 398 ist ein Verfahren und eine Vorrichtung zur Programmierung von nichtflüchtigen Speichern im Zusammenhang mit Steuergeräten für Brennkraftmaschinen bekannt. Das beschriebene Verfahren arbeitet mit einem Mikrorechner, wobei der Mikrorechner die zu programmierenden Daten von einem externen Programmiergerät bitseriell empfängt und ein Programmodul abarbeitet, um die Daten in den nichtflüchtigen Speicher einzuschreiben.

Der Mikrorechner steht mit einem flüchtigen Speicher in Verbindung, in den Programme, die von dem Mikrorechner ausgeführt werden können, einlesbar sind. Das Programmodul wird vor dem Programmiervorgang in den flüchtigen Speicher geladen und der Mikrorechner durch das Programmodul derart konfiguriert, daß er die zu programmierenden Daten synchron von dem Programmiergerät empfängt.

Als vorteilhaft ist beschrieben, daß das Programmodul zur Programmierung des nichtflüchtigen Speichers nicht in einem maskenprogrammierten Speicher enthalten sein muß. Da die gesamte Fahrsoftware in den nichtflüchtigen Speicher eingeschrieben wird, kann sogar ein maskenprogrammierter Speicher ganz entfallen.

Flashbausteine sind in kleinste unabhängig zu programmierende Speichereinheiten (Pages) aufgeteilt. Dies bedeutet, daß immer, wenn ein Teil dieser Page programmiert werden soll, die gesamte Page programmiert werden muß. Das Löschen solcher Bausteine erfolgt sektorweise. Diese Sektoren umfassen in der Regel viele Pages.

Ein Folge hieraus ist, daß Informationen, welche nicht zum selben Zeitpunkt zur Verfügung stehen, nicht innerhalb einer Page abgelegt werden können. Dies stellt ein Problem, insbesondere bei der Ablage von verketteten Listen, dar.

Verkettete Listen stellen eine platzsparende Möglichkeit zur Ablage von Daten zur Verfügung, welche zugleich eine zeitliche als auch eine logische Ordnung besitzen.

Die Ablage erfolgt also in zwei Dimensionen, wobei nicht notwendigerweise ein zweidimensionales Feld die effektivste Ablagemöglichkeit darstellt, wie nachfolgend aufgezeigt:

Das einfachste Verfahren zur Ablage von N Werten ist ein eindimensionales Array der Länge N. Müssen zusätzlich, wie im folgenden Fall, mehrere Instanzen eines Wertes abgelegt werden, kann dazu ein zweidimensionales N.M Array verwendet werden. Der Index m

(m = 0, . . ., M - 1)

spezifiziert dabei die Instanz des Wertes n

(n = 0, . . ., N - 1).

Die Größe N liegt durch die Anzahl der in einem Datensektor abzulegenden Werte fest. Die Größe M, und damit die Anzahl der maximal pro Wert in einem Datensektor speicherbaren Instanzen, wird durch den zur Verfügung stehenden Speicherplatz S - ausgedrückt in Einheiten der Größe eines Arrayelements - festgelegt.

Bei zweidimensionalen Arrays ist von Nachteil, daß bei häufiger Änderung eines der Werte aufgrund des vorgegebenen, begrenzten Umfangs der Arrays kein Speicherplatz mehr zur Verfügung steht. Damit müssen für die Speicherung weiterer Instanzen des Werts die aktuellen Instanzen aller Werte auf einen anderen Datensektor übertragen werden, obwohl der zur Verfügung stehende Speicherplatz von insgesamt N.M Instanzen nur zu einem Bruchteil belegt ist.

Wenn die verschiedenen Zeilen oder Spalten des Feldes unterschiedliche Größen haben, eignen sich sogenannte verkettete Listen zur Ablage der Daten.

Verkettete Listen sind ein gut geeigneter Ansatz zur Ablage von einer im voraus nicht bestimmbaren Anzahl von Instanzen mehrerer Werte. Bei verketteten Listen wird für jede Instanz eines jeden Werts ein Zeiger, bzw. ein Verweis, auf die nächste Instanz dieses Werts geführt. Ein spezieller Zeigerzustand wird zur Kodierung für den Fall verwendet, dass die zugehörige Instanz die aktuellste des jeweiligen Werts ist. Als Verweis müssen dabei relative oder absolute Adressen verwendet werden.

Bei einer verketteten Liste wird somit zusammen mit einer jeweils abgelegten Informationseinheit ein Verweis auf die Ablagestelle der jeweils nächsten, logisch verknüpften Informationseinheit gespeichert. Im günstigsten Fall werden die Ablagestellen erst zu dem Zeitpunkt belegt, zu dem die zu speichernde Information zur Verfügung steht. So ist es möglich, dieser Information die jeweils nächste, freie Ablagestelle zuzuweisen. Dieses Vorgehen führt zu einer lückenlosen Nutzung des Speichers.

Nachteilig dabei ist, daß die Informationen für den Verweis erst zu einem späteren Zeitpunkt zur Verfügung stehen als die zuvor gespeicherten Daten. Dies bedeutet, daß für die beiden Informationen getrennt programmierbare Speichereinheiten (Pages) zur Verfügung stehen müssen. Hieraus folgt, daß für m gespeicherte Informationen mindestens 2 m-1 Speichereinheiten (Pages) zur Verfügung stehen müssen, da bis auf die letzte gespeicherte Informationseinheit alle vorherigen Informationseinheiten den Platz für einen folgenden Verweis reservieren müssen. Dies ist unabhängig von der Anzahl der zu speichernden Werte. Lediglich die Summe aller gespeicherten Instanzen über alle Werte ist entscheidend.

Üblicherweise werden verkettete Listen jedoch verwendet, um möglichst viele Instanzen relativ kleiner Informationseinheiten zu speichern, d. h. daß m sehr groß ist. Daher ist der Verlust durch diese Speicheraufteilung äußerst groß.

Vorteile der Erfindung

Das erfindungsgemäße Verfahren dient zur Ablage von Daten in einen Speicherbaustein. Dieser ist in mehrere unabhängig voneinander zu programmierende Speichereinheiten (Pages) aufgeteilt.

Bei dem Verfahren wird eine Anzahl von veränderlichen Werten gespeichert und bei Änderung eines bereits abgespeicherten Werts eine neue Instanz des Werts erzeugt und in einer Speichereinheit im Speicherbaustein abgelegt. Die Instanzen jedes Werts werden als verkettete Liste abgelegt, d. h. daß jeder Instanz eines Werts ein Verweis zugeordnet ist, der auf die nächste Instanz des Werts, soweit vorhanden, verweist. Für den Fall, daß keine nächste Instanz vorhanden ist, das bedeutet, daß die Instanz den aktuellen Wert wiedergibt, ist der Verweis entsprechend kodiert.

Das erfindungsgemäße Verfahren zeichnet sich dadurch aus, daß beim Abspeichern einer Instanz in eine erste Speichereinheit gleichzeitig eine zweite Speichereinheit belegt wird und in die erste Speichereinheit die Instanz und ein Verweis auf die zweite Speichereinheit abgelegt werden.

Es wird somit bei der Speicherung einer Instanz, d. h. bei der Speicherung einer Informationseinheit, in einer Speichereinheit zum gleichen Zeitpunkt eine weitere, freie Speichereinheit belegt. Dadurch kann der Verweis gleichzeitig mit der sonst zuvor gespeicherten Informationseinheit abgelegt werden und somit auch in der selben Speichereinheit gespeichert werden. Durch diese Reservierung wird pro Wert eine zusätzliche Speichereinheit benötigt. Somit müssen für N unabhängig zu speichernde Werte N zusätzliche Speichereinheiten reserviert werden. Der Speicherverbrauch beträgt also m + N Speichereinheiten.

Für m << N < = 1 kann gegenüber dem früher verwendeten Verfahren eine Speicherersparnis von bis zu

erzielt werden.

Das erfindungsgemäße Verfahren kommt insbesondere bei der Ablage von Daten in Flashspeicherbausteine zur Anwendung. Diese können nämlich nicht byte- oder wortweise wiederholt beschrieben werden. Flashbausteine sind in unabhängig voneinander zu programmierende Speichereinheiten unterteilt, die vor Ändern ihres Inhalts gelöscht werden müssen.

Erfindungsgemäß ist eine Programmiervorrichtung zur Ablage von Daten in einen Speicherbaustein, der in mehrere unabhängig voneinander zu programmierende Speichereinheiten aufgeteilt ist, vorgesehen. Diese Programmiervorrichtung weist Mittel zur Durchführung des Verfahrens nach Anspruch 1 auf.

Der Speicherbaustein kann mit einer parallelen Busschnittstelle mit separaten Adress- und Datenbussen oder durch eine serielle Busschnittstelle, wie beispielsweise I²C oder SPI (serial peripheral interface), angesteuert werden.

Ein erfindungsgemäßes Computerprogramm weist Programmcode- Mittel auf, um alle Schritte des erfindungsgemäßen Verfahrens nach Anspruch 1 durchzuführen.

Das Computerprogramm kann auf geeigneten Datenträgern, wie EEPROMs, Flash-Memories aber auch CD-ROMs, Disketten oder Festplattenlaufwerken gespeichert sein.

Zeichnung

Die Erfindung wird anhand der beigefügten Zeichnung näher erläutert. In der Zeichnung zeigt:

Fig. 1 eine bevorzugte Ausführungsform der erfindungsgemäßen Programmiervorrichtung in schematischer Darstellung im Einsatz,

Fig. 2 die Ablage von Werten in einer verketteten Liste auf herkömmliche Weise, und

Fig. 3 die Ablage von Werten in einer verketteten Liste gemäß einer bevorzugten Ausführungsform des erfindungsgemäßen Verfahrens.

Fig. 1 zeigt in schematischer Darstellung eine bevorzugte Ausführungsform der erfindungsgemäßen Vorrichtung, insgesamt mit der Bezugsziffer 10 bezeichnet, im Einsatz.

Zu erkennen ist die Programmiervorrichtung 10, die über eine Datenleitung 11 mit einem Speicherbaustein 12, typischerweise einem Flashbaustein, verbunden ist.

Die Programmiervorrichtung 10 weist einen Mikroprozessor 13, eine Speichereinrichtung 14 und einen Datenbus 15 auf. Über den Datenbus 15 ist der Mikroprozessor 13 mit der Speichereinrichtung 14 verbunden und es erfolgt über diesen die Kommunikation zwischen dem Mikroprozessor 13 und der Speichereinrichtung 14.

Der Speicherbaustein 12 enthält in diesem Fall eine parallele Busschnittstelle 16 und typischerweise mehrere unabhängig voneinander zu programmierende Speichereinheiten 17.

Zur Ablage der Daten in dem Speicherbaustein 12 werden diese vom Programmiergerät 10 mittels eines auf dem Mikroprozessor 13 ablaufenden Computerprogramms über die Datenleitung 11 und die parallele Busschnittstelle 16 übertragen und in den Speichereinheiten 17 abgespeichert. Bei dem erfindungsgemäßen Verfahren wird in eine der Speichereinheiten 17, die als erste Speichereinheit 17 bezeichnet wird, eine Instanz mit einem Verweis abgespeichert, und gleichzeitig eine weitere der Speichereinheiten 17 belegt, die als zweite Speichereinheit 17 bezeichnet wird. Der Verweis zeigt auf diese zweite Speichereinheit 17.

Fig. 2 verdeutlicht die Speicherung von Werten in einer verketteten Liste nach dem herkömmlichen Verfahren. Hierzu ist schematisch ein Speicherbaustein, insgesamt mit der Bezugsziffer 20 bezeichnet, dargestellt.

Zur Verdeutlichung sind in Fig. 2 eine erste Spalte 21 und eine zweite Spalte 22 dargestellt. In der ersten Spalte 21 sind a-Speichereinheiten 23 gezeigt. Jede der a- Speichereinheiten 23, bis auf die mit "frei" bezeichneten, enthält eine Informationseinheit, nämlich eine Instanz eines Werts. Somit befinden sich in den a-Speichereinheiten 23 sämtliche Instanzen aller Werte in chronologischer Reihenfolge.

In der zweiten Spalte sind b-Speichereinheiten 24 dargestellt, die, bis auf die mit "frei" bezeichneten, jeweils eine Informationseinheit, nämlich jeweils einen Verweis, enthalten. Dabei ist jede b-Speichereinheit 24 einer a-Speichereinheit 23 zugewiesen. Die oberste a- Speichereinheit 23 enthält beispielsweise die Instanz 0 des Werts 0. Die zugehörige b-Speichereinheit 24, ebenfalls die oberste in Fig. 2, enthält einen Verweis, der, wie mit einem Pfeil 25 verdeutlicht, auf die nächste Instanz, die Instanz 1, des Werts 0 zeigt.

Für jede Instanz eines jeden Werts wird ein Zeiger auf die nächste Instanz dieses Wertes geführt. Ein bestimmter Zeigerzustand, beispielsweise FFFF₁₆, wird zur Kodierung für den Fall verwendet, dass die zugehörige Instanz die aktuellste des jeweiligen Werts ist. In Fig. 2 ist dies mit "- - -" verdeutlicht.

Für m gespeicherte Informationseinheiten müssen also 2 m - 1 Speichereinheiten zur Verfügung stehen.

In Fig. 3 ist die Ablage von Werten in einer verketteten Liste gemäß einer bevorzugten Ausführungsform des erfindungsgemäßen Verfahrens dargestellt.

Der in Fig. 3 in schematischer Darstellung gezeigte Speicherbaustein ist insgesamt mit dem Bezugszeichen 30 bezeichnet.

Wiederum ist eine erste Spalte 31 und eine zweite Spalte 32 zu erkennen. Die erste Spalte enthält jedoch erste Informationseinheiten 33 und die zweite Spalte zweite Informationseinheiten 34.

Die ersten Informationseinheiten 33 stellen die Instanzen der Werte die zweiten Informationseinheiten 34 die Verweise dar.

Es wird verdeutlicht, daß jeweils eine erste Informationseinheit 33 und eine zweite Informationseinheit 34 in einer Speichereinheit 35 enthalten sind. Die Speichereinheiten 35 in Fig. 3 entsprechen den Speichereinheiten 17 aus Fig. 1. Die Verweise von einer ersten Speichereinheit 35 zu einer zweiten Speichereinheit 35 sind mit Pfeilen 36 verdeutlicht.

Gemäß dem erfindungsgemäßen Verfahren wird bei der Speicherung einer Instanz eines Werts zum gleichen Zeitpunkt eine weitere, freie Speichereinheit 35 belegt. So kann der Verweis gleichzeitig mit der beim herkömmlichen Verfahren zuvor gespeicherten Informationseinheit abgelegt werden. Durch diese Reservierung wird pro Wert eine zusätzliche Speichereinheit 35 benötigt. Für N unabhängig zu speichernde Werte müssen N zusätzliche Speichereinheiten 35 reserviert werden. Der Speicherverbrauch beträgt also m + N Speichereinheiten 35.

Gegenüber dem herkömmlichen Verfahren wird also eine Speicherersparnis von bis zu

erreicht.

Das erfindungsgemäße Verfahren ermöglicht eine möglichst flexible Datenablage für verkettete Listen in Speicherbausteinen, welche nicht auf Byte- oder Wortebene lösch- oder programmierbar sind, wobei eine erhebliche Einsparung an Speicherplatz erzielt wird.

Claims (8)

1. Verfahren, zur Ablage von Daten in einen Speicherbaustein (30), der in mehrere unabhängig voneinander zu programmierende Speichereinheiten (17, 35) aufgeteilt ist, wobei eine Anzahl von veränderlichen Werten gespeichert wird und bei Änderung eines bereits abgespeicherten Werts eine neue, nächste Instanz des Werts erzeugt und in einer Speichereinheit (17, 35) im Speicherbaustein (30) abgelegt wird, und die Instanzen eines Werts als verkettete Liste abgelegt werden, bei der jeder Instanz eines Werts ein Verweis zugeordnet ist, der auf die nächste Instanz des Werts, soweit vorhanden, verweist, dadurch gekennzeichnet, daß beim Abspeichern einer Instanz in eine erste Speichereinheit (17, 35) gleichzeitig eine zweite Speichereinheit (17, 35) belegt wird und in die erste Speichereinheit (17, 35) die Instanz und ein Verweis auf die zweite Speichereinheit (17, 35) abgelegt werden.

2. Verfahren nach Anspruch 1, dadurch gekennzeichnet, daß die Verweise jeweils einen bestimmten Code aufweisen, falls die zugehörige Instanz den aktuellsten Wert wiedergibt.

3. Verfahren nach Anspruch 1 oder 2, dadurch gekennzeichnet, daß als Speicherbaustein (30) ein Flashbaustein eingesetzt wird.

4. Programmiervorrichtung (10) zur Ablage von Daten in einem Speicherbaustein (30), der in mehrere unabhängig voneinander zu programmierende Speichereinheiten (17, 35) aufgeteilt ist, bei der die Programmiervorrichtung (10) Mittel zur Durchführung des Verfahrens nach einem der Ansprüche 1 bis 3 aufweist.

5. Programmiervorrichtung (10) nach Anspruch 4, gekennzeichnet durch eine parallele Busschnittstelle (16).

6. Programmiervorrichtung (10) nach Anspruch 4, gekennzeichnet durch eine serielle Busschnittstelle.

7. Computerprogramm mit Programmcode-Mitteln, um alle Schritte des Anspruchs 1 durchzuführen, wenn das Computerprogramm auf einem Computer oder einer entsprechenden Rechnereinheit, insbesondere einer Einheit in einer Programmiervorrichtung (10) nach einem der Ansprüche 4 bis 6, durchgeführt wird.

8. Computerprogrammprodukt mit Programmcode-Mitteln, die auf einem computerlesbaren Datenträger gespeichert sind, um das Verfahren nach einem der Ansprüche 1 bis 3 durchzuführen, wenn das Computerprogramm auf einem Computer oder einer entsprechenden Rechnereinheit, insbesondere einer Einheit in einer Programmiervorrichtung (10) nach einem der Ansprüche 4 bis 6, durchgeführt wird.