DE69506158T2

DE69506158T2 - Fahrzeuglokalnetz und Nachrichtenleitweglenkungsverfahren

Info

Publication number: DE69506158T2
Application number: DE69506158T
Authority: DE
Inventors: William V. Ann Arbor 48103 Michigan Luitje
Original assignee: Chrysler Corp
Current assignee: FCA US LLC
Priority date: 1994-03-31
Filing date: 1995-03-30
Publication date: 1999-06-24
Anticipated expiration: 2015-03-31
Also published as: DE69506158D1; CA2145916C; US5701418A; EP0675024A1; AU1509395A; CA2145916A1; AU676423B2; JPH0895609A; EP0675024B1

Description

Die vorliegende Erfindung betrifft die Nachrichtenlenkung in lokalen Netzwerken (LANs), und im Besonderen betrifft die vorliegende Erfindung den Einsatz von Hash-Funktionen für Tabellenverweise durch Mikrocontrollermodule, die mit einem fahrzeuginternen lokalen Netzwerk verbunden sind.
In automatisierten Fertigungsstätten und anderen ähnlichen Umgebungen konnte festgestellt werden, daß eine effiziente Betriebsweise die Verteilung von Steuerfunktionen innerhalb der Umgebung umfaßt. Dies wird durch den Einsatz einer Mehrzahl entfernt voneinander angeordneter Mikrocomputer erreicht, die für die Abwicklung spezieller Funktionen programmiert sind. Zur Koordinierung des Betriebs sind die Mikrocomputer über ein lokales Netzwerk ("LAN") miteinander verbunden, und wobei einer oder mehrere überwachende Mikrocomputer ebenfalls mit dem LAN verbunden sein können. Ein Beispiel für ein derartiges System zum Einsatz in einer automatisierten Fertigungsstätte wird in dem U.S. Patent US-A- 4.972.367 an Burke offenbart. In diesem Patent wird das Problem der verringerten Leistungsfähigkeit auf Grund der Notwendigkeit zur Übertragung zahlreicher Nachrichten bzw. Meldungen über das lokale Netzwerk erkannt.
Die Mikrocontroller-Bauelemente innerhalb eines Fahrzeugs führen normalerweise eine Vielzahl von Aufgaben aus, wie etwa die Steuerung des Motors, die Erzeugung von Pausenzeichen, die Überwachung verschiedener Fahrzeugfunktionen, die Erzeugung akustischer Nachrichten, usw. Viele dieser Mikrocontroller- Bauelemente müssen mit anderen Mikrocontroller-Bauelementen in dem Fahrzeug kommunizieren. Zum Beispiel kann ein erster Mikrocontroller ein Problem erkennen, wie etwa einen zu niedrigen Öldruck, wobei dieses bestehende Problem einem zweiten Mikrocontroller gemeldet werden muß, der die Erzeugung einer akustischen Meldung an den Fahrer steuert. Nach Empfang der Information erzeugt das zweite Mikrocontroller-Bauelement die akustische Meldung bzw. Nachricht.
Die Notwendigkeit der Kommunikation zwischen den Mikrocontroller-Bauelementen innerhalb eines Fahrzeugs hat zu der Einführung von fahrzeuginternen lokalen Netzwerken geführt, durch welche die in einem Fahrzeug an verschiedenen Positionen angeordneten Mikrocontroller-Bauelemente in der Lage sind, miteinander zu kommunizieren. Daraus resultiert, daß jedes der Mikrocontroller-Bauelemente in dem Netzwerk bestimmen muß, auf welche Meldungen, die über das lokale Netzwerk übertragen werden, das Bauelement in welcher Weise reagieren muß.
Ob sich das lokale Netzwerk in einer Fertigungsstätte, in einem Fahrzeug oder in einer anderen Umgebung befindet, in jedem Fall müssen die Probleme der Kommunikation zwischen den Mikrocontrollern über das lokale Netzwerk überwunden werden. Bei einem Verfahren, das dies erreichen soll, wird die übermittelte Meldung mit einer Mikrocontroller-Zieladresse oder einer Mikrocontroller-Kennung versehen. In diesem Fall untersuchen die Mikrocontroller in dem lokalen Netzwerk jede eingehende Meldung, vergleichen deren Adresse mit der Adresse, mit der die Meldung versehen war, und bestimmen sofort, ob es sich bei der Meldung um eine Meldung für den jeweiligen Mikrocontroller handelt. Bei diesem Prinzip wird allerdings nicht die Situation berücksichtigt, bei der eine Meldung eine Reaktion von mehr als einem Mikrocontroller erfordert. Außerdem ist dieses System nicht besonders flexibel. Wenn eine Funktion zum Beispiel von einem Mikrocontroller zu einem anderen übertragen wird, so müssen alle Mikrocontroller, die Meldungen übertragen, die sich auf diese Funktion beziehen, modifiziert werden.
Außerdem ist für ein Adreßsystem ein sehr großer Rechneraufwand erforderlich. Ein Mikrocontroller, der ein Problem beim Fahrzeugbetrieb erfaßt, muß zum Beispiel so programmiert werden, daß er die angemessene bzw. die zweckmäßige Reaktion ebenso kennt wie die Adresse der anderen Mikrocontroller, die diese Reaktion bzw. das Ansprechverhalten ausführen müssen. Ein System mit einem solchen sehr umfassenden Rechneraufwand wird in dem U.S. Patent US-A- 5.117.458 an Takaragi et al. beschrieben.
In einem Ansatz ein flexibleres System mit geringerem Rechneraufwand vorzusehen, können die Nachrichten mit Nachrichtenkennungen (IDs) versehen werden, welche die Nachricht und nicht den Ziel-Mikrocontroller identifizieren. Eine derartige Technik wird in dem U.S. Patent US-A-5.095.480 an Fenner offenbart. Bei dieser Anordnung muß jeder Mikrocontroller des lokalen Netzwerks eine von dem jeweiligen Mikrocontroller geführte Tabelle durchsuchen, die alle Nachrichtenkennungen aufweist, auf die der jeweilige Mikrocontroller ansprechen muß, um dadurch festzustellen, ob die Nachricht für diesen Mikrocontroller bestimmt ist oder nicht. Die Tabelle kann ferner andere Parameter aufweisen, die erforderlich sind, um entsprechend auf eine bestimmte Nachricht anzusprechen. Normalerweise muß ein Mikrocontrollermodul auf mehr als eine Nachrichtenart mit unterschiedlichen Parametervoraussetzungen ansprechen.
Die Einführung von Fahrzeug-Multiplexnetzwerken in Motorfahrzeuge hat dazu geführt, daß diese das Netzwerk verwendenden Bauelemente bzw. Module eine Vielzahl von Tabellenverweisen durchführen müssen. Die Hauptaufgabe dabei ist es, die Nachrichten zu finden, die Parameter der Nachrichten zu bestimmen und Informationen zu lokalisieren, die Aufschluß darüber geben, wie die entsprechende Nachricht zu verarbeiten ist. Ein weiterer Grund für die Tabellenverweise ist die Verarbeitung von Diagnoseanfragen, die häufig nach Parameterinformationen über eine Parameterkennung fragen. Dabei wird erneut auf eine Tabelle zugegriffen, um die Position des Parameters, dessen Skalierung, usw. herauszufinden. Dieser vermehrte Einsatz von Tabellenverweisen bzw. Tabellenzugriffen bedeutet, speziell während der Verarbeitung des normalen Multiplex- Netzwerkverkehrs, daß ein nicht unwesentlicher Anteil der Mikroprozessorzeit für Tabellenzugriffe bzw. für Tabellenverweise in Anspruch genommen wird. Wenn es eine Möglichkeit gäbe, diese Tabellenzugriffe schneller durchzuführen, so könnte der Mikroprozessor seine Zeit mit produktiveren Arbeiten verbringen, wie etwa mit der Steuerung eines Motors oder Getriebes.
Ein herkömmliches Verfahren für das Suchen von Informationen in einer Tabelle ist die lineare Suche. Nachrichtenkennungen und Informationen werden in einer Tabelle gespeichert, wobei die am häufigsten auftretenden Nachrichtenkennungen normalerweise am Tabellenanfang gespeichert werden. Diese Einträge werden nacheinander überprüft, bis der passende Eintrag gefunden wird, oder bis die ganze Tabelle durchsucht worden ist und kein passender Eintrag gefunden worden ist. Ein Problem bei der linearen Suche in Tabellen ist die große Inanspruchnahme des Controllers oder Prozessors, d.h. der Mikrocontroller verbringt seine Zeit mit der Ausführung von Suchfunktionen anstatt mit der Ausführung seiner eigentlichen Hauptaufgabe.
Der große Gesamtaufwand bei einer linearen Tabellensuche kann unter Annahme einiger Beispiele veranschaulicht werden. In den nachstehenden Beispielen werden die folgenden Annahmen zugrunde gelegt. Die Verweistabelle weist vier Bytes pro Eintrag auf, mit einem Byte für die Kennung (ID), einem Byte für die Nachrichtenlänge und zwei Bytes für die Adresse der Nachrichtenleistungsroutine. Die Codebeispiele sind in der Assemblersprache Motorola 68HC11 geschrieben. Zum Zwecke des Vergleichs der Ausführungszeiten unterschiedlicher Tabellenverweisverfahren wird davon ausgegangen, daß 68HC11 mit 8 MHz ausgeführt wird, so daß ein Zyklus der CPU 0,5 Mikrosekunden dauert. Die Tabellen weisen unabhängig von dem verwendeten Verweis- bzw. Zugriffsverfahren die gleichen Informationen auf, die allerdings unterschiedlich angeordnet sein können.
Bei dem Tabellenzugriffscode, der in einer kennzeichnenden Steuereinheit bzw. einem Controller eines Fahrzeugs eingesetzt wird, handelt es sich um eine einfache Schleife, die die empfangenen Kennungen mit Einträgen in einer Tabelle vergleicht. Die Kennungen werden normalerweise derart in der Tabelle angeordnet, daß sich die Nachrichten mit den höchsten Frequenzen nahe des Tabellenanfangs befinden. In Tabelle 1 ist eine kennzeichnende Implementierung bzw. Umsetzung eines linearen Tabellenzugriffs dargestellt. TABELLE 1. 68HC11 CODE FÜR DEN LINEAREN TABELLENZUGRIFF
Die Tabelle veranschaulicht die für die Verarbeitung einer Kennung (ID) erforderliche Zeit. Hiermit wird festgestellt, daß die ersten drei Zeilen die Schleife aufbauen, wobei die Ausführung 4 Mikrosekunden in Anspruch nimmt. Die Zeilen 4-8 (8,5 Mikrosekunden) werden für jeden Tabelleneintrag einmal ausgeführt, der nicht mit der empfangenen Kennung übereinstimmt, bis die ganze Tabelle überprüft worden ist. Somit beträgt die Gesamtzeit zur Verarbeitung einer nicht in der Tabelle vorhandenen Kennung (ID) 4 + 8,5 · (# Tabelleneinträge). Bei 12 Tabelleneinträgen beträgt die erforderliche Zeit zum Beispiel 106 Mikrosekunden. Einige Fahrzeugsteuereinheiten empfangen bis zu 20 Kennungen, so daß die Verarbeitung einer empfangenen Kennung im schlechtesten Fall 174 Mikrosekunden in Anspruch nimmt. Dies entspricht einer langen Bindungs- bzw. Belegungszeit für einen Echtzeit- Controller.
Die für die Suche nach Kennungen erforderliche Zeit kann grob als prozentualer Anteil der Zeit des Prozessors geschätzt werden. Wenn eine durchschnittliche Nachrichtenlänge von drei Byte, eine LAN-Bitrate von 7812,5 Bits pro Sekunde und eine 35prozentige Bus-Beschäftigungszeit angenommen werden, so werden etwa 68 Nachrichten pro Sekunde über den Bus übertragen. Wenn 106 Mikrosekunden 68mal pro Sekunde verwendet werden, so verbringt der Prozessor mehr als 0,7% seiner Zeit nur mit der Sortierung der Nachrichten von dem lokalen Netzwerk. Wenn 174 Mikrosekunden verwendet werden, so steigt diese Zahl auf nahezu 1,2%. Hiermit wird festgestellt, daß es sich dabei um Zahlen für den schlechtesten aller Fälle handelt. In der Realität ignoriert kein Modul alle Nachrichten auf dem Bus, so daß einige der Kennungen in der Tabelle gefunden werden, bevor die maximale Zeit in Anspruch genommen worden ist. Außerdem muß ein Modul nicht jede Nachricht verarbeiten, die es übermittelt.
Die "Hash-Codierung" hat sich als wirksames Mittel zum Suchen in einer Tabelle bewährt. Bei der Hash-Codierung wird eine arithmetische Funktion bzw. eine Hash-Funktion für die Erzeugung eines Codes bzw. eines Schlüssels verwendet, der für eine Nachrichtenkennung steht. Wenn die Hash-Funktion bei einer hash-codierten empfangenen Kennung angewandt wird, so handelt es sich bei dem Ergebnis um einen Zeiger in eine für den Mikrocomputer vorgesehene Tabelle, der den Abschnitt der Nachricht anzeigt. Verfahren für den Erhalt einer geeigneten Hash-Funktion für eine bestimmte Anwendung sind allgemein bekannt. Beispiele für diese Methoden werden in zwei hierin durch Verweis enthaltenen Dokumenten beschrieben: Reciprocal Hashing: A Method for Generating Minimal Perfect Hashing Functions, von G. Jaeschke, Co mm. ACM 24, 12 (Dezember 1981), 829-833; und Perfect Hashing Functions: A Single Probe Retrieving Method for Static Sets, von R. Sprugnoli, Comm. ACM 20, 11 (November 1977), 841-850.
Die Grundidee der Hash-Codierung ist die Erfassung des in der Tabelle zu findenden Elements sowie die Ausführung bestimmter numerischer Berechnungen (die Hash-Funktion) an diesem Element, um dadurch eine Tabellenadresse zu ermitteln. Hash- Funktionen werden seit den Anfängen des Computerzeitalters für Tabellenabfragen verwendet. Am häufigsten werden sie bei Großrechnern für Compiler und Datenbanken eingesetzt, und es existiert umfassende Literatur über die verschiedenen Verwendungsmöglichkeiten von Hash-Funktionen. Ein Großrechner unterscheidet sich allerdings erheblich von einem Mikrocontroller: der Speicher zum Speichern der Tabellen ist deutlich größer, es existieren periphere Speichervorrichtungen und die CPU ist mit dem vollen Komplement schneller, höchst präziser Rechenbefehle ausgestattet. Außerdem sind viele bestehende Hash-Funktionen speziell für dynamische Systeme ausgerichtet, wobei Elemente einer Tabelle hinzugefügt und aus dieser entfernt werden.
Der Einsatz des Hash-Filterns in einer LAN-Umgebung wird in dem Bezugsdokument Mini-Micro Conference Record, November 1983, offenbart, wobei Ethernet/IEEE 802.3 in Bezug auf eine Größtintegrationsumsetzung (VLSI) behandelt wird. Der Stationsadressen-Erfassungsabsohnitt offenbart, daß eine Zieladresse im Ethernet durch ein Feld mit einer Breite von 48 Bit definiert ist, wobei ein erstes Bit anzeigt, ob es sich bei der Adresse um eine physikalische oder um eine Multicast- Adresse handelt. Die allgemeine Adressierung ist ein Sonderfall der Multicast-Adressierung, wobei ein Datenpaket an alle Knoten übermittelt werden kann, d.h. an alle Computerstationen im Netzwerk. Ein LAN-Controller für Ethernet (LANCE) sorgt für eine Abbildung von 2&sup4;&sup7; möglichen Adressen auf 26 Adressen, wobei dieser Vorgang als Hash-Filtern bezeichnet wird. Auf diese Weise wird die 47-Bit-Zieladresse (D) durch die Funktion "f" bearbeitet, so daß f(D) D in eine Vergleichstabelle in dem LANCE abbildet, wodurch mit gewisser Wahrscheinlichkeit festgestellt werden kann, daß D eine gültige Adresse darstellt. Danach führt der Prozessor einen perfekten Filtervorgang an D durch, wobei die eigenen Verweistabellen in dem Speicher dafür eingesetzt werden, festzustellen, ob das Paket verwendet wird. Auf Grund eines unvollkommenen Filtervorgangs kann der LANCE gewisse nicht adressierte Pakete zulassen, die durch Filtern des Prozessors aussortiert werden. Wenn die Anzahl der logischen Adressen in dem Netzwerk (LAN) insgesamt niedriger ist als 64, so können diese auf eine Art und Weise zugewiesen werden, wobei der Hash-Filter als perfekter bzw. vollkommener Filter funktionsfähig ist, wobei kein zusätzlicher Filter erforderlich ist. Das Hash-Filtern verringert den Softwareaufwand an dem Prozessor bei einer willkürlichen Adressenverteilung mindestens um einen Faktor von 64.
Vorgesehen ist gemäß der vorliegenden Erfindung ein Steuersystem mit Bestandteilen sowie mit mindestens zwei Verarbeitungseinheiten, die jeweils mit einer Nachrichtenkennung identifizierte Nachrichten erzeugen, und die einem Speicher zugeordnet sind, der eine Nachrichtenkennungstabelle speichert, welche die zugeordnete Verarbeitungseinheit verarbeiten kann, wobei jede der in der genannten Tabelle gespeicherten Nachrichtenkennungen eine Eintragung in der genannten Tabelle darstellt, wobei die genannten Verarbeitungseinheiten als ein lokales Netzwerk miteinander verbunden sind, das Nachrichten zwischen den genannten Verarbeitungseinheiten überträgt, dadurch gekennzeichnet, daß es sich bei jeder der genannten Verarbeitungseinheiten um einen Mikrocontroller handelt, der so konfiguriert ist, daß er der genannten Nachrichtenkennung jeder über das genannte lokale Netzwerk empfangenen Nachricht eine Hash-Funktion zuweist, um einen Tabellenindex zu erzeugen, um den entsprechenden jeweiligen Mikrocontroller zu einem bestimmten Eintrag in einer in dem genannten Speicher gespeicherten Tabelle zu leiten sowie zum Vergleichen des genannten speziellen Eintrags mit der Nachrichtenkennung einer der genannten empfangenen Nachrichten, die bereits mit der genannten Hash-Funktion bearbeitet worden ist, wobei jeder der genannten Mikrocontroller Informationen zur Steuerung der genannten Bestandteile des Steuersystems verarbeitet und die genannten Nachrichten erzeugt, die sich auf einen Steuerungszustand eines anderen der genannten Mikrocontroller bezieht, und wobei jeder der genannten Mikrocontroller auf die genannte empfangene Nachricht durch Verarbeitung von Befehlen anspricht, die sich auf den genannten speziellen Eintrag in der Tabelle beziehen, wenn der genannte spezielle Eintrag in der Tabelle mit der Nachrichtenkennung übereinstimmt, die durch die genannte Hash-Funktion bearbeitet wird.
Vorgesehen ist gemäß einem weiteren Aspekt der vorliegenden Erfindung ein Verfahren zur Steuerung von Nachrichten in einem lokalen Netzwerk mit Verarbeitungseinheiten, wobei jede der genannten Verarbeitungseinheiten zur Ausführung einer vorbestimmten Funktion funktionsfähig ist und einem Speicher zugeordnet ist, der eine Hash-Tabelle von Nachrichtenkennungen speichert, die jeweils einen Eintrag in der Hash-Tabelle darstellen, und wobei die Einheiten so konfiguriert sind, daß sie bestimmen, ob eine in dem genannten lokalen Netzwerk übermittelte Nachricht mit einer Nachrichtenkennung von einer anderen der genannten Verarbeitungseinheiten zu verarbeiten ist, gekennzeichnet durch die Verarbeitung der genannten Nachrichten, wobei es sich bei jeder der genannten Verarbeitungseinheiten um einen Mikrocontroller handelt; die Ausübung einer vordefinierten Hash-Funktion an der genannten Nachrichtenkennung, sowie die Bestimmung eines Hash- Tabellenindexes daraus; die Verwendung der genannten vordefinierten Hash-Funktion in Verbindung mit dem genannten Hash-Tabellenindex zur Bestimmung eines Platzes in der genannten Hash-Tabelle; das Vergleichen des genannten Eintrags, der an dem genannten Platz gespeichert ist, mit der genannten Nachrichtenkennung; und die Ausführung der genannten vorbestimmten Funktion auf der Basis von in dem Speicher gespeicherten Informationen, die sich auf den Eintrag beziehen, wenn der genannte Eintrag und die genannte Nachrichtenkennung, die durch die genannte vordefinierte Hash- Funktion bearbeitet werden, identisch sind.
Die vorstehenden und andere Merkmale der vorliegenden Erfindung werden aus der folgenden genauen Beschreibung der bevorzugten Ausführungsbeispiele in Verbindung mit den beigefügten Zeichnungen noch besser verständlich. Es zeigen:
Fig. 1 ein Blockdiagramm eines erfindungsgemäßen fahrzeuginternen lokalen Netzwerks;
Fig. 2 ein Flußdiagramm eines Verfahrens zum Speichern von Nachrichtenkennungen unter Verwendung von Hash-Funktionen;
Fig. 3 ein Flußdiagramm eines Verfahrens zur Bestimmung, ob eine Nachricht zu bearbeiten ist; und
die Fig. 4 bis 7 ein Flußdiagramm eines Verfahrens zur Bestimmung der Parameterwerte für eine lineare, kongruente Hash-Funktion.
Die Abbildung aus Fig. 1 veranschaulicht Mikrocontrollermodule 10 in einem fahrzeuginternen lokalen Netzwerk 25. Diese Mikrocontroller steuern jeweils einzeln bestimmte Funktionen des Fahrzeugs, wie zum Beispiel die Funktionsweise des Motors oder die Aufzeichnung bestimmter Zustände. Als Folge erzeugen die Mikrocontroller Nachrichten, die entweder weitere Funktionen anderer Mikrocontroller erforderlich machen oder lediglich über einen Zustand informieren. Diese Ausgangsnachrichten sind nicht an einen bestimmten Mikrocontroller in dem lokalen Netzwerk adressiert, sie sind jedoch mit Nachrichtenkennungen versehen, die die Art der Nachricht anzeigen. Danach ist es Aufgabe der anderen Mikrocontroller festzustellen, ob sie auf der Basis der Nachricht eine Funktion ausüben müssen. Dies stellt der jeweilige Mikrocontroller durch Überprüfung fest, ob eine Nachricht mit dieser Kennung in einer dem Mikrocontroller zugeordneten Tabelle gespeichert ist. Jeder Mikrocontroller 10 ist mit einem statischen Speicher oder ROM-Speicher 5 vorgesehen, der eine Nachrichtentabelle aufweist. Die Nachrichten werden unter Verwendung einer Hash-Funktion in den Tabellen in den ROM-Speichern 5 gespeichert und abgerufen.
Die Abbildung aus Fig. 2 zeigt ein Flußdiagramm eines bevorzugten Ausführungsbeispiels eines Verfahrens zum Speichern von Nachrichtenkennungen, d.h. einer Hash-Funktion. Bei der Funktion handelt es sich gemäß der Darstellung um eine lineare, kongruente Hash-Funktion, wobei die Hash-Funktion in der folgenden Form gegeben ist:
Index = (A*ID) + B
wobei die numerischen Werte von A und B von den zu speichernden IDs (Kennungen), der Tabellengröße und den Größen der Tabelleneinträge abhängig sind. Die Tabelle 2 entspricht der Tabelle 1 und zeigt, wie die Hash-Funktion anzuwenden ist. TABELLE 2. 68HC11 CODE FÜR DIE LINEARE KONGRUENTE HASH- FUNKTION
Die Zeilen 1-4 aus Tabelle 2 werden im Geradeausverfahren implementiert, wobei die Index-Bits im oberen Teil des Registers B verbleiben. In Zeile 5 wird der Index für eine Tabelle mit 16 Einträgen extrahiert, und in den Zeilen 6-7 wird der Index an die entsprechende Position für die Adressierung einer Tabelle mit vier Byte Einträgen bewegt. In den Zeilen 8-9 wird der Index zum Tabellenanfang addiert. Schließlich wird in den Zeilen 10-12 die empfangene Kennung (ID) mit dem Tabelleneintrag verglichen. Wenn diese zusammenpassen, wird die Nachricht danach gemäß den Informationen in der Tabelle verarbeitet; wenn sie nicht zusammenpassen, kann die Nachricht ignoriert werden. Es ist notwendig die epmfangene Kennung mit der Kennung in der Tabelle zu vergleichen, da die Hash-Funktion eine Verdichtungsfunktion darstellt. In diesem Beispiel werden 256 mögliche Kennungen in eine Tabelle mit 16 Einträgen abgebildet, so daß mehrere Kennungen in jeden Tabelleneintrag abgebildet werden. Jedoch wird nur eine der Kennungen in der Liste der Kennungen, die von dem Modul empfangen werden, in einen bestimmten Tabelleneintrag abgebildet.
In dem Code gibt es keine Schleifen oder Verzweigungen, so daß alle Kennungen innerhalb der gleichen Zeit verarbeitet werden, d.h. 19,5 Mikrosekunden, und zwar ungeachtet der Tatsache, ob sie sich in der Tabelle befinden oder nicht. Dieses Verfahren der linearen, kongruenten Hash-Funktion ist mit dem dem Stand der Technik entsprechenden linearen Suchverfahren aus Tabelle 1 bezüglich der Ausführungszeit bei 2 oder mehr Einträgen in der Tabelle leistungsmäßig vergleichbar. In Bezug auf die vorstehend beschriebene Tabelle mit 12 Einträgen ist das Verfahren der kongruenten Hash-Funktion gemäß der vorliegenden Erfindung 5mal so schnell wie die lineare Tabellensuche gemäß dem Stand der Technik (d.h. Tabelle 1).
Zur weiteren Veranschaulichung des Verfahrens wird angenommen, daß die Fahrzeugsteuereinheit 12 hexadezimale ("hex") Kennungen aufweist. Die lineare, kongruente Hash-Funktion mit A = hex 5B und B = 4 veranschaulicht eine perfekte Hash- Funktion für die folgende Liste von 12 einzugebenden Kennungen (IDs)
02 50 56 84 8C A4 B2 B4 CA DA E4 EC.
Wenn die Kennung (ID) A4 von einem Mikrocontroller empfangen wird, wird sie mit 5B multipliziert (was zu hex 3A4C führt) und addiert, so daß 3A50 resultiert. Zeile 5 aus Tabelle 2 eliminiert alles außer den vier werthöchsten Bits des niedrigen Bytes dieses Produkts, und die folgenden Zeilen passen das Ergebnis für eine zweckmäßige Indexierung einer Tabelle mit 4 Byte Einträgen an. Dies entspricht einer Extrahierung der zweiten hexadezimalen Stelle von rechts, die 5 entspricht, sowie der Verwendung dieser als Relativzeiger in die vorstehend gegebene Tabelle. Bei einem Zählbeginn bei 0 befindet sich A4 bei dem fünften Eintrag in der Tabelle. Die anderen Kennungen erzeugen unter Verwendung dieser Formel ebenfalls Relativzeiger, wobei dies für eine vollkommene Hash- Funktion erforderlich ist; es gibt 12 Kennungen, wobei die Tabelle eine Länge von 16 Einträgen aufweist. Da 00 eine ungültige Kennung darstellt, werden ungenutzte Tabelleneinträge mit 00 gefüllt.
Bei einer ausreichend großen Tabelle ist es immer möglich, eine vollkommene bzw. perfekte Hash-Funktion zu finden. Wenn die Kennungen zum Beispiel eine Länge von 8 Bits aufweisen, so kann die Kennung als eine Adresse in einer Tabelle mit 256 Einträgen verwendet werden. Abhängig von der Gruppe der Kennungen, für die eine Hash-Funktion gesucht wird, besteht allerdings keine Gewährleistung, daß eine perfekte Hash- Funktion für eine Tabelle entsprechender Größe gefunden wird. Wenn ferner etwa große räumliche Einschränkungen gegeben sind, so kann es wünschenswert sein, eine kleine Tabelle zu verwenden, die nicht alle erforderlichen Kennungen aufweist. In diesen Fällen können auf einfache Weise fest codierte Kontrollen für die wenigen Kennungen durchgeführt werden, die mit der gewünschten Hash-Funktion nicht funktionieren. Die lineare, kongruente Hash-Funktion funktioniert weiterhin außerordentlich gut mit ID-Listen aus realen Mikrocontroller- Anwendungen.
In dem Flußdiagramm der Abbildung aus Fig. 2 wird die Umsetzung von Tabelle 2 in Software veranschaulicht. In dem Schritt 21 wird eine Kennung in ein Register geladen. Als nächstes wird das Register mit hex 5B multipliziert (Schritt 22) und 4 hinzu addiert (Schritt 23). Danach erfolgt in dem Schritt 24 eine UND-Verknüpfung des Registers mit hex F0, wodurch nur die oberen vier Bits oder die Tetrade des niederwertigen Bytes erhalten werden. Diese Bits stellen die Stelle dar, an der die Kennung gespeichert werden soll, wenn zum Beispiel die Tetrade 5 entspricht, so sollte die Kennung den sechsten Eintrag in der Tabelle darstellen (dabei wird davon ausgegangen, daß der erste Eintrag 0 ist). Danach muß der Versatz von dem Tabellenanfang errechnet werden. Somit muß die Tetrade mit der Größe des Eintrags, die vier Bytes entspricht, multipliziert werden. Da sich der Index in Schritt 24 weiterhin in der oberen Tetrade des niederwertigen Bytes befindet, wird das Register in dem Schritt 25 um zwei Bits nach rechts verschoben, an Stelle einer Division durch 16, gefolgt von einer Multiplikation mit 4. Dabei ergibt sich jedoch das gleiche Ergebnis. Der Registerinhalt weist jedoch jetzt die Verschiebung bzw. den Versatz von dem Tabellenanfang auf, wo die Kennung und die zugehörigen Daten gespeichert werden sollen.
Sobald die Kennungen gespeichert sind, kann ein Mikroprozessor mit der Untersuchung der über das lokale Netzwerk übertragenen Nachrichtenkennungen beginnen und bestimmen, ob als Reaktion ein Ansprechverhalten vorgenommen werden muß. Die Abbildung aus Fig. 3 zeigt ein Flußdiagramm, in dem veranschaulicht wird, wie diese Bestimmung durchgeführt wird. Jeder Mikroprozessor untersucht die über das Netzwerk übertragene Nachrichtenkennung (Schritt 31). Als nächstes führt der Mikroprozessor an der Kennung die entsprechende Hash-Funktion aus (Schritt 32). Unter Verwendung der Ausgabe der Funktion als Versatzadresse vergleicht der Mikroprozessor die empfangene Nachrichtenkennung mit der an der Versatzadresse gespeicherten Nachrichtenkennung (Schritt 33). Wenn diese übereinstimmen, führt der Mikroprozessor die entsprechende Funktion aus (Schritt 34), wobei die Nachricht ansonsten ignoriert wird (Schritt 35).
Wie dies aus Tabelle 3 ersichtlich ist, kann durch das lineare, kongruente Hash-Verfahren eine minimale perfekte Hash-Funktion für eine Fahrzeugsteuereinheit sowie nahezu minimale perfekte Hash-Funktionen für andere Module erzeugt werden. Die Spalten "Alle bis auf 2 fitted" und "Alle bis auf 1 fitted" zeigen, daß manchmal auch eine wesentlich kleinere Tabelle verwendet werden kann, wenn nicht alle Kennungen über die Hash-Funktion verarbeitet werden. Speziell gilt, daß eine Tabellengröße von 27 für eine perfekte Hash-Funktion erforderlich ist, wobei eine Tabellengröße von nur 18 für eine nahezu perfekte bzw. vollkommene Hash-Funktion erforderlich ist, die 16 der 18 Kennungen verarbeitet. TABELLE 3. Kleinste notwendige Tabellengröße für verschiedene Fit-Level unter Verwendung einer linearen, kongruenten Hash- Funktion
Bei dem Beispielcode wird von einer Tabellengröße von 16 ausgegangen sowie von einer Datensatzgröße in Zweierpotenz. Diese Werte müssen generalisiert werden. Bei anderen Tabellengrößen in Zweierpotenz kann die UND-Funktion weiterhin für die Extrahierung von Index-Bits verwendet werden, wenn die Konstante in Zeile 5 aus Tabelle 2 so geändert wird, daß die Anzahl der extrahierten Bits log&sub2; (Tabellengröße) entspricht. Bei einer Tabellengröße von 32 muß die Konstante zum Beispiel $F8 lauten. Wenn die Tabellengröße keiner Zweierpotenz entspricht, so muß ein etwas umfangreicher Code verarbeitet werden, d.h. die Zeile 5 aus Tabelle 2 muß durch die folgenden Zeilen ersetzt werden:
Wenn die Datensatzgröße keiner Zweierpotenz entspricht, so müssen die Zeilen 6 und 7 aus Tabelle 2 durch die folgenden Zeilen ersetzt werden:
In bestimmten Situationen ist es möglich, diese beiden multiplikativen Operationen durch den Schritt der einmaligen Multiplikation mit der Konstanten TblSize * RecSize zu verknüpfen.
Durch diese Generalisierungen werden der Hash-Funktion Anweisungen hinzugefügt. Andererseits kann möglicherweise eine Hash-Funktion gefunden werden, die einen oder mehrere Parameter aufweist, die Null entsprechen. In diesen Fällen können die Anweisungen, die diese Parameter implementieren, weggelassen werden.
Dem Fachmann ist es bekannt, daß es neben den veranschaulichten Hash-Funktionen eine Vielzahl bekannter Hash-Funktionen gibt, die ebenfalls verwendet werden können. Eine weitere bekannte Hash-Funktion ist eine multiplikative exklusive ODER-Funktion ("XOR") mit:
Index = (A * ID) B
wobei die XOR-Operation darstellt. Für die Codierung dieser Funktion wird die ADD Anweisung aus Zeile 4 in Tabelle 2 einfach durch eine XOR Anweisung ersetzt. Die Wirksamkeit der multiplikativen XOR-Methode ist in Tabelle 5 dargestellt. TABELLE 5. Kleinste notwendige Tabellengröße für verschiedene Fit-Level unter Verwendung einer linearen, kongruenten Hash- Funktion
Eine weitere Hash-Funktion wird als lineare, kongruente Funktion mit XOR bezeichnet. Dabei werden die Ideen der ersten beiden Funktionen verknüpft. Sie lautet:
Index = (A * ID) B
wobei die XOR Operation darstellt. Für die Codierung dieser Funktion wird die folgende Anweisung einfach nach Zeile 4 aus Tabelle 2 eingefügt.
Diese Funktion ist effektiver als die lineare, kongruente Hash-Funktion und die multiplikative exklusive ODER-Hash- Funktion, wobei dies auf Kosten einer längeren Suchzeit sowie einer etwas längeren Ausführungszeit geht. Die Ergebnisse dieser Funktion bei einer Testdatenreihe sind nachstehend aufgeführt. TABELLE 6. Kleinste notwendige Tabellengröße für verschiedene Fit-Level unter Verwendung einer linearen, kongruenten Hash- Funktion mit XOR-Hash-Funktion
Es muß noch eine weitere Hash-Funktion erwähnt werden, die reziproke Hash-Funktion. Diese Hash-Funktion weist verschiedene Nachteile auf:
- Sie verwendet eine Divisionsanweisung, die bei Mikrocontrollern wesentlich seltener ist als die Multiplikationsanweisung.
- Die Ausführung der Division braucht selbst wenn sie verfügbar ist länger als eine Multiplikation (41 Zyklen gegenüber 10 Zyklen in MC68HC11).
- Es sind zwei Divisionen erforderlich, wenn die Tabellengröße keiner Zweierpotenz entspricht.
- Sie ist höchstens so effektiv wie die einfacheren Hash- Funktionen.
Die Funktion sollte allein schon deshalb erwähnt werden, weil sie in manchen Fällen nützlich ist. Diese Hash- Funktionstechnik wird in dem folgenden Artikel umfassend beschrieben: "Reciprocal Hashing: A Method for Generating Minimal Perfect Hashing Functions", von G. Jaeshke in Communications of the ACM, Ausgabe 24, Nummer 12 (Dezember 1981). Dieses Verfahren wird durch die folgende Gleichung beschrieben:
Index = (A / ID) mod (Tabellengröße)
Die MC68HC11 Umsetzung dieser Methode für eine Tabelle mit 16 Elementen ist in Tabelle 7 dargestellt.
; Valid.
Länge,
Kontroll-
summe,
usw. TABELLE 7. 68HC11 Code für die reziproke Hash-Funktion
Wie dies in Tabelle 8 dargestellt ist, ist die Ermittlung perfekter Hash-Funktionen etwas weniger effektiv als bei der vorstehend beschriebenen linearen, kongruenten Funktion mit XOR-Methode. TABELLE 8. Kleinste notwendige Tabellengröße für verschiedene Fit-Level unter Verwendung einer reziproken Hash-Funktion
Für die entsprechende Umsetzung der vorstehend beschriebenen Techniken ist ein Verfahren erforderlich, mit dem die geeigneten Hash-Funktionen ermittelt werden können. In den Abbildungen aus den Fig. 4 bis 7 wird ein Verfahren zur Ermittlung der geeigneten Parameterwerte für eine bestimmte Gruppe von Kennungen unter Verwendung einer linearen, kongruenten Hash-Funktion veranschaulicht.
In Bezug auf die Abbildungen aus den Fig. 4 bis 7 werden die Parameterindizes A, B und der maximale Zählwert initialisiert (Schritt 41). A und B weisen letztendlich die geeigneten Parameter für die gegebene Gruppe von IDs auf. Die ganze Gruppe der Kennungen wird danach in ein Feld eingelesen (Schritte 42-44). A1 und B1 werden danach initialisiert (Schritt 47) und weisen die Parameterwerte auf, die geprüft werden. Danach wird die ganze Tabelle initialisiert, wobei alle Tabelleneinträge auf Null gesetzt werden (Schritte 48- 51). Unter Verwendung von Al und B1 als Parameterwerte und unter Verwendung jeder Kennung werden die Tabellenindizes unter Verwendung einer linearen, kongruenten Hash-Formel berechnet (Schritte 53-62). Wenn für einen Index der Tabelleneintrag gleich Null ist, so wird die Kennung in dem Tabelleneintrag gespeichert (Schritte 54-55) und gezählt. Wenn die Anzahl der gespeicherten Einträge größer ist als der gesamte Zählwert der unter Verwendung einer anderen Gruppe von Parameterwerten gespeicherten Kennungen, so wird A auf A1 und B auf B1 gesetzt, und der Zählwert wird gespeichert (Schritte 63-64). A1 wird danach erhöht (Schritt 65), die Tabelleneinträge werden erneut initialisiert (Schritte 48-51) und die Kennungen werden alle erneut geprüft (Schritte 53-62). Dies wird solange durchgeführt, bis A1 gleich 256 ist (Schritt 66). Danach wird A1 auf Null gesetzt und B1 wird erhöht (Schritt 71). Die Tabelleneinträge werden erneut initialisiert (Schritte 48-51) und die Kennungen werden geprüft (Schritte 53-62). Dieser Prozeß dauert solange an, bis alle möglichen Kombinationen der Werte für A1 und B1 geprüft worden sind. Nachdem alle Werte geprüft worden sind weisen A und B die besten Parameterwerte für eine lineare, kongruente Hash- Funktion auf.
Der Fachmann erkennt, daß das Flußdiagramm aus den Fig. 4 bis 7 mit einigen Modifikationen auch für die anderen beschriebenen Hash-Funktionen verwendet werden kann.
Die vorliegende Erfindung wurde vorstehend zwar speziell in Bezug auf bevorzugte Ausführungsbeispiele beschrieben und dargestellt, jedoch wird der Fachmann erkennen, daß verschiedene Abänderungen bezüglich der Ausführung und der Einzelheiten durchgeführt werden können, ohne dabei von dem in den Ansprüchen definierten Umfang der Erfindung abzuweichen.

Claims

1. Steuersystem mit Bestandteilen sowie mit mindestens zwei Verarbeitungseinheiten, die jeweils mit einer Nachrichtenkennung identifizierte Nachrichten erzeugen, und die einem Speicher (5) zugeordnet sind, der eine Nachrichtenkennungstabelle speichert, welche die zugeordnete Verarbeitungseinheit verarbeiten kann, wobei jede der in der genannten Tabelle gespeicherten Nachrichtenkennungen eine Eintragung in der genannten Tabelle darstellt, wobei die genannten Verarbeitungseinheiten als ein lokales Netzwerk (25) miteinander verbunden sind, das Nachrichten zwischen den genannten Verarbeitungseinheiten überträgt, dadurch gekennzeichnet, daß es sich bei jeder der genannten Verarbeitungseinheiten um einen Mikrocontroller (10) handelt, der so konfiguriert ist, daß er der genannten Nachrichtenkennung jeder über das genannte lokale Netzwerk (25) empfangenen Nachricht eine Hash- Funktion zuweist, um einen Tabellenindex zu erzeugen, um den entsprechenden jeweiligen Mikrocontroller (10) zu einem bestimmten Eintrag in einer in dem genannten Speicher (5) gespeicherten Tabelle zu leiten sowie zum Vergleichen des genannten speziellen Eintrags mit der Nachrichtenkennung einer der genannten empfangenen Nachrichten, die bereits mit der genannten Hash-Funktion bearbeitet worden ist, wobei jeder der genannten Mikrocontroller (10) Informationen zur Steuerung der genannten Bestandteile des Steuersystems verarbeitet und die genannten Nachrichten erzeugt, die sich auf einen Steuerungszustand eines anderen der genannten Mikrocontroller (10) bezieht, und wobei jeder der genannten Mikrocontroller (10) auf die genannte empfangene Nachricht durch Verarbeitung von Befehlen anspricht, die sich auf den genannten speziellen Eintrag in der Tabelle beziehen, wenn der genannte spezielle Eintrag in der Tabelle mit der Nachrichtenkennung übereinstimmt, die durch die genannte Hash-Funktion bearbeitet wird.

2. Steuersystem nach Anspruch 1, dadurch gekennzeichnet, daß das lokale Netzwerk (25) und die Mikrocontroller (10) ein fahrzeuginternes Steuersystem für ein Fahrzeug bilden.

3. Steuersystem nach Anspruch 1 oder 2, dadurch gekennzeichnet, daß es sich bei der Hash-Funktion um eine lineare kongruente Hash-Funktion handelt.

4. Steuersystem nach Anspruch 1 oder 2, dadurch gekennzeichnet, daß es sich bei der Hash-Funktion um eine multiplikative exklusive ODER-Hash-Funktion handelt.

5. Steuersystem nach Anspruch 1 oder 2, dadurch gekennzeichnet, daß es sich bei der Hash-Funktion um eine reziproke Hash-Funktion handelt.

6. Steuersystem nach Anspruch 1, dadurch gekennzeichnet, daß jeder der Mikrocontroller (10) einen programmierten Mikroprozessor aufweist.

7. Verfahren zur Steuerung von Nachrichten in einem lokalen Netzwerk mit Verarbeitungseinheiten, wobei jede der genannten Verarbeitungseinheiten zur Ausführung einer vorbestimmten Funktion funktionsfähig ist und einem Speicher zugeordnet ist, der eine Hash-Tabelle von Nachrichtenkennungen speichert, die jeweils einen Eintrag in der Hash-Tabelle darstellen, und wobei die Einheiten so konfiguriert sind, daß sie bestimmen, ob eine in dem genannten lokalen Netzwerk übermittelte Nachricht mit einer Nachrichtenkennung von einer anderen der genannten Verarbeitungseinheiten zu verarbeiten ist, gekennzeichnet durch

die Verarbeitung der genannten Nachrichten, wobei es sich bei jeder der genannten Verarbeitungseinheiten um einen Mikrocontroller handelt;

die Ausübung einer vordefinierten Hash-Funktion an der genannten Nachrichtenkennung, sowie die Bestimmung eines Hash- Tabellenindexes daraus;

die Verwendung der genannten vordefinierten Hash-Funktion in Verbindung mit dem genannten Hash-Tabellenindex zur Bestimmung eines Platzes in der genannten Hash-Tabelle;

das Vergleichen des genannten Eintrags, der an dem genannten Platz gespeichert ist, mit der genannten Nachrichtenkennung; und

die Ausführung der genannten vorbestimmten Funktion auf der Basis von in dem Speicher gespeicherten Informationen, die sich auf den Eintrag beziehen, wenn der genannte Eintrag und die genannte Nachrichtenkennung, die durch die genannte vordefinierte Hash-Funktion bearbeitet werden, identisch sind.

8. Verfahren nach Anspruch 7, dadurch gekennzeichnet, daß es sich bei der vordefinierten Hash-Funktion um eine lineare kongruente Hash-Funktion handelt.

9. Verfahren nach Anspruch 7, dadurch gekennzeichnet, daß es sich bei der vordefinierten Hash-Funktion um eine multiplikative exklusive ODER-Funktion handelt.

10. Verfahren nach Anspruch 7, dadurch gekennzeichnet, daß es sich bei der vordefinierten Hash-Funktion um eine reziproke Hash-Funktion handelt.

11. Verfahren nach einem der Ansprüche 7 bis 10, dadurch gekennzeichnet, daß es sich bei dem lokalen Netzwerk um ein fahrzeuginternes lokales Netzwerk handelt, das die Funktionsweise eines Fahrzeugs steuert.