Universität Stuttgart
Permanent URI for this communityhttps://elib.uni-stuttgart.de/handle/11682/1
Browse
12 results
Search Results
Item Open Access Contributions to low energy consumption in digital circuits(2000) Bühler, Markus; Baitinger, Utz G. (Prof. Dr.-Ing)After bipolar, static PMOS, and NMOS technologies have been widely replaced by static CMOS, static current has practically disappeared in digital circuits. Thus, the problem of power consumption was thought to be solved. However, with increasing integration densities and operation frequencies, combined with the advent of complex portable devices, design for low power has regained its importance as the third design goal, beside delay and area consumption. But in contrast to the past, today, dynamic power consumption is dominant by far. The domain of low power design can be divided into two major subdomains: power estimation and actual circuit design for low power, the latter including all efforts for power optimization and low power synthesis. In this thesis, specific aspects of both subdomains are treated on different levels. The design aspect is covered by an investigation of suitable circuit techniques for a novel, 3D, T-gate, SOI technology. It was found that DPL fits best the structural requirements of this technology but consumes 50 more power than static CMOS. The consequences are discussed in the text. The main focus of this thesis is put on power estimation techniques on gate level. A novel, set based simulation method is presented and extended for real delay gate models (RDM). Several further optimization methods are proposed. It is shown that the RDM extension can also be applied to bitparallel logic simulators. As a last extension the set based approach is combined with probabilistic simulation methods, thus making it possible to take into account signal correlations during probabilistic estimation.Item Open Access Die geregelte logische Uhr, eine globale Uhr für die tracebasierte Überwachung paralleler Anwendungen(2000) Rabenseifner, Rolf; Rothermel, Kurt (Prof. Dr.)Das Aufzeichnen und Darstellen des Programmflusses sowie des Nachrichtenaustauschs paralleler Anwendungen ist schwierig, wenn jeder Prozessor eine eigene Uhr besitzt, und diese Uhren nicht synchronisiert sind. Mehrere Strategien zur Bildung einer globalen Uhrzeit werden in einem Überblick dargestellt, und die Grenzen werden aufgezeigt. Die geregelte logische Uhr, eine neue Methode auf der Basis von Lamports logischer Uhr, wird vorgestellt. Ungenaue Zeitstempel aus Tracefiles werden derart modifiziert, daß sie die Uhrenbedingung erfüllen, d.h. daß der Empfang einer Nachricht einen späteren Zeitstempel als das zugehörige Sendeereignis besitzt. Mit dem Regler wird das Maximum aller lokalen Prozessoruhren als Basis für eine globale Zeit angenähert. Die korrigierten Zeitstempel ermöglichen Leistungsmessungen, bei denen die Ereignisse in verschiedenen Prozessen liegen. Eine stückweise lineare rückwärtige Amortisation der Uhrenkorrekturen garantiert, daß die Fehler bei Messungen von Zeitintervallen zwischen Ereignissen im selben Prozeß minimal sind. Bei der Erstellung eines Tracefiles ist kein zusätzlicher Protokollaufwand nötig. Die geregelte logische Uhr kann als Filter für Tracefiles implementiert werden. Sie kann aber auch in Monitor- und Debuggingwerkzeuge integriert werden.Item Open Access Gleichungen mit regulären Randbedingungen über freien Gruppen(2000) Hagenah, Christian; Diekert, Volker (Prof. Dr.)Wir beweisen, daß das Erfüllbarkeitsproblem für Gleichungen mit regulären Randbedingungen über freien Gruppen PSPACE-vollständig ist. Wir zeigen auch, daß eine minimale Lösung einer solchen Gleichung höchstens eine doppelt exponentielle Länge hat und in 2-DEXPTIME berechnet werden kann. Wir reduzieren zuerst das Problem Gleichungen mit regulären Randbedingungen über einer freien Gruppen zu lösen auf das Problem Gleichungen mit regulären Randbedingungen über freien Monoiden mit einer Anti-Involution zu lösen. Anschließend stellen wir einen Algorithmus vor, der in PSPACE entscheidet, ob diese Gleichungen lösbar sind und einen Algorithmus, der in 2-DEXPTIME eine Lösung berechnet, wenn die Gleichung lösbar ist.Item Open Access Hierarchische Graphen zur Wegesuche(2000) Buchholz, Friedhelm; Claus, Volker (Prof. Dr.)In dieser Arbeit wird ein Zwei-Phasenmodell zur effizienten Entfernungsberechnung in gewichteten Graphen untersucht. Bekannte Anwendungsgebiete sind Verkehrsinformationssyteme, VLSI Design, Verteiltes Rechnen und geometrische und parallele Algorithmen. In einer Preprocessing-Phase wird zu einem Graphen ein Hierarchischer Graph (HG) konstruiert, der in der Online-Phase zur Entfernungsberechnung eingesetzt wird. Es werden die Laufzeit (T) der Preprocessing-Phase, die Groesse (S) des HG'en und die Laufzeit (Q) der Online-Phase untersucht. Zwei kontraere Modellierungsansaetze werden vorgestellt: Geeignete Knoten und ein rekursives Separationskonzept. Das Konzept mit Geeigneten Knoten wird auf Levelgraphen verallgemeinert und es wird gezeigt, dass die Berechnung einer minimalen Geeigneten Knotenmenge NP-vollstaendig ist. Die Approximation bzgl. der Groesse der Geeigneten Knotenmenge kann bis auf einen logarithmischen Faktor und bezueglich des Umgebungsabstands bis auf einen konstanten Faktor in polynomieller Laufzeit durchgefuehrt werden. Im Falle von planaren Graphen wird mittels eines erweiterten Separationskonzepts (Ideen von Lingas 1990 und von Didjev 1996 werden kombiniert) gezeigt, dass HG'en von fast linearer Groesse genuegen, um Q in O(n {1.5} log 3 n) zu gewaehrleisten. Dieses Resultat ist modulo logarithmischer Faktoren optimal. Ausserdem wird ein neuer Parameter 'Separatorweite' fuer Graphen eingefuehrt und es wird konstruktiv gezeigt, dass die Separatorweite unabhaengig von der Baumweite ist, aber hoechstens um einen logarithmischen Faktor von der Baumweite abweicht. Am Beispiel wird gezeigt, dass eine logarithmische Abweichung auftreten kann.Item Open Access Ressourcenreservierung und Task-Plazierung in verteilten Multimedia-Systemen(1999) Dermler, Gabriel; Rothermel, Kurt (Prof. Dr.)In dieser Arbeit werden grundlegende Aspekte der Dienstgüteerbringung für verteilte Multimedia-Anwendungen untersucht. Aufbauend auf einer Anwendungsmodellierung in Form von Flußgraphen, die aus Verarbeitungskomponenten zusammengesetzt werden, sowie einer Dienstgütearchitektur, die Dienstgütebegriffe auf der Anwendungs- und der Systemebene unterscheidet, werden Konzepte und Lösungen erarbeitet, die eine garantierte und optimierte Bereitstellung von Dienstgüte ermöglichen. Einen Schwerpunkt bilden Protokolle zur Reservierung von Ressourcen, die auf komplexe Flußgraphen anwendbar sind. Die Protokolle erlauben individuelle Dienstgütevorgaben an den Senken eines Flußgraphen und berücksichtigen die Verfügbarkeit von Rechner- und Netzwerkressourcen sowie funktionale Einschränkungen, die durch das Design der Komponenten definiert sind. Ferner sind sie unabhängig von der Verteilung der Komponenten auf Rechnern eines verteilten Systems anwendbar und in der Lage Dienstgütegarantien sicherzustellen. Als ein zweiter Schwerpunkt werden Mechanismen zur Plazierung von Anwendungskomponenten vorgestellt, die eine optimale Ausnutzung von Ressourcen in einem verteilten System sicherstellen. Hierzu werden Algorithmen zur Berechnung günstiger Plazierungen entwickelt und bewertet. Ferner wird ein Protokoll vorgestellt, welches zur Instanziierung eines Flußgraphen verwendet werden kann. Auf der Grundlage der vorgestellten Konzepte wird die Beziehung zwischen der Plazierung eines Flußgraphen sowie der erforderlichen Ressourcenreservierung dargestellt.Item Open Access Auswirkungen verschiedener Informationsebenen auf die Effizienz der dynamischen Lastbalancierung(1999) Pollak, Rainer; Reuter, Andreas (Prof. Dr.)Parallele und verteilte Systeme gewannen im Laufe der letzten Jahre, aufgrund der Entwicklung immer leistungsfähigerer Hardware und Kommunikationsmedien, zunehmend an Bedeutung. Um die enorme Leistungsfähigkeit dieser Systeme nutzen zu können, ist es erforderlich, die zur Verfügung stehenden Ressoucen des parallelen bzw. verteilten Systems möglichst gleichmäßig auszulasten. Aufgabe eines dynamischen Lastbalancierers ist es deshalb, die zur Verarbeitung anstehenden Anwendungen möglichst gleichmäßig auf die zur Verfügung stehenden Ressourcen zu verteilen. Insbesondere sollte ein dynamischer Lastbalancierer seine Aufgabe weitgehend transparent für den Anwender erledigen. Einen entscheidenden Einfluß auf die Leistungsfähigkeit eines dynamischen Lastbalancierers hat die zur Verfügung stehende entscheidungsrelevante Information. Die vorliegende Arbeit beschäftigt sich aus diesem Grund mit der Frage, inwieweit ein dynamischer Lastbalancierer in der Lage ist, Informationen aus unterschiedlichen Quellen mit unterschiedlichen Eigenschaften, effizient zu verarbeiten. Dazu wird in einem ersten Schritt die für einen dynamischen Lastbalancierer verfügbare Information klassifiziert. Das Klassifikationsergebnis sind die vier sogenannten Informationsebenen. Da die Untersuchung mit bereits existierenden parallelen Anwendungen durchgeführt werden soll, wird anschließend die hierarchische Lastbalancierungsumgebung PaLaBer (Paralleler LastBalancierer) vorgestellt, die im Hinblick auf diese Untersuchung entwickelt wurde. Die PaLaBer-Umgebung ermöglicht es, parallele Anwendungen ohne nennenswerte Modifikationen des Quelltextes mit Hilfe eines dynamischen Lastbalancierers zu unterstützen.Item Open Access Konzepte und Techniken der Datenversorgung für komponentenbasierte Informationssysteme(1999) Sellentin, Jürgen; Mitschang, Bernhard (Prof. Dr.-Ing. habil.)Rechnergestützte Informationssysteme stellen heutzutage für viele Branchen ein unverzichtbares Hilfsmittel dar. Ohne sie wäre die Komplexität von Abläufen und die damit verbundene Menge von Daten kaum noch zu bewältigen. Dieser Sachverhalt trifft insbesondere für die Entwicklung neuer Produkte zu, bei der zunächst extrem viele Daten aus vorangegangenen Arbeiten und zugrundeliegenden Richtlinien zu berücksichtigen sind. Gleichzeitig entsteht während der Entwicklung eine Menge neuer Daten, die später als Grundlage der Produktion dienen. Wir betrachten deshalb rechnergestützte Entwurfsumgebungen als repräsentatives Beispiel für datenintensive Informationssysteme, bei denen sowohl große Mengen von Daten gelesen als auch erzeugt bzw. geschrieben werden. Anhand dieses Szenarios werden wir deshalb die einzelnen Aspekte und Probleme diskutieren und verdeutlichen. Neben der reinen Diskussion von Datenversorgungsstrategien wollen wir weiterhin ausgewählte Methoden anhand eines Prototypen evaluieren. Als Basis dient uns dabei die neu entwickelte Anbindung des SDAI (Standard Data Access Interface) von STEP an die Sprache Java (ISO 10303-27). Diese wurde im Rahmen der vorliegenden Arbeit wesentlich mitgestaltet und ermöglicht den simultanen Zugriff auf unterschiedliche Datenquellen über unterschiedliche Datenversorgungsstrategien. Wir werden mit unseren Prototypen zwei verschiedene CORBA-basierte Lösungen einem JDBC-basierten Ansatz gegenüberstellen. Die Datenquellen und ihre Zugriffsschnittstellen sind dabei als sog. Data Modules in die SDAI-Schnittstelle integriert. Es zeigt sich, daß CORBA unter gewissen Umständen zur Realisierung einer effizienten Datenversorgung benutzt werden kann, das zugrundeliegende Modell aber nicht dem eigentlichen Grundgedanken von CORBA entspricht. Insbesondere lassen sich nur wenige der standardisierten CORBA-Komponenten (sog. Services und Facilities) benutzen.Item Open Access Einbettung von Interpolationsfunktionen in die Datenbanksprache SQL - Datenbankunterstützung für die Umweltforschung(2000) Zink, Leonore; Reuter, Andreas (Prof. Dr.)Diese Arbeit begann im Rahmen des interdisziplinären Umweltforschungsprojekts "Naturmeßfeld 'Horkheimer Insel'", das sich aus fünf Anwenderprojekten und einem Informatik-Teilprojekt zusammensetzte. Innerhalb dieses Projekts wurden von allen Anwendern unterschiedlichste Meßwerte erhoben. Zur Speicherung der Daten wurde ein relationales Datenbanksystem gewählt, weil die Strukturierung, die Sicherung und inzwischen auch die Verteilung der Daten durch ein verteiltes Datenbanksystem zufriedenstellend abgedeckt werden. Nur für die Aufbereitung speziell von Umweltdaten und Meßwerten werden noch immer keine geeigneten Werkzeuge oder Ergänzungen zu den Datenbanksystemen angeboten. Nun sind Meßreihen aus der natürlichen Umwelt oft unvollständig, weil die Ergebnisse einzelner Messungen fehlen, oder die zeitlichen bzw. räumlichen Abstände der Meßwerte können nicht in der vom weiterverarbeitenden Programm gewünschten Form geliefert werden. Hier setzt diese Arbeit an: Durch in das Datenbanksystem integrierte Interpolationsverfahren wird es möglich, Werte an beliebigen Punkten des Meßintervalls innerhalb einer "normalen" Datenbankanfrage abzufragen. Die Werte werden dann aus den umliegenden Meßwerten mit einem geeigneten Verfahren berechnet. In dieser Arbeit wird beschrieben, wie eine Anfragesprache erweitert werden muß, damit solche Anfragen möglich sind, und wie dazu das Datenbanksystem ergänzt werden muß. Verschiedene mögliche Ansätze werden aufgezeigt. Ein Ansatz wurde als Prototyp implementiert, um die Benutzerfreundlichkeit dieses Konzepts zu zeigen. Die Leistungsmessungen an einigen Beispielanfragen belegen ein akzeptables Antwortzeitverhalten.Item Open Access Parallelisierung eines komplexen Finite-Elemente-Programmsystems(2000) Nölting, Swen; Argyris, John (em. Prof. Dr. Dr. h. c. mult.)In der vorliegenden Arbeit wird ein Konzept zur Parallelisierung des nicht-linearen Finite-Elemente Paketes FEPS auf Parallelrechnern mit verteiltem Speicher entwickelt. Mit dem Ziel, eine weitgehende Automatisierung der parallelen Berechnungen zu ermöglichen, werden dabei alle Teilschritte der Simulation in das Konzept mit einbezogen. Die wichtigsten Bausteine des Gesamtsystems - ein paralleler Netzgenerierungsalgorithmus, parallele FE-Module und eine Kommunikationsbibliothek - werden implementiert und anhand von Test- und Praxisbeispielen erprobt. Der parallele Netzgenerierungsalgorithmus basiert auf der rekursiven Zweiteilung der das Rechengebiet definierenden geometrischen Struktur vor der eigentlichen Generierung der Gitterpunkte. Dieses Vorgehen beschleunigt die Netzgenerierung und erlaubt vor allem die Erstellung von Teilgebieten, die ein besseres Lastgleichgewicht der späteren FE-Berechnungen gewährleisten als dies mit konventionellen Netzaufteilungsalgorithmen möglich ist.Item Open Access Atomic architectural component recovery for program understanding and evolution(2000) Koschke, Rainer; Plödereder, Erhard (Prof. Dr.)Die Fülle der publizierten Techniken zur Komponentenerkennung macht eine Klassifikation und Bewertung notwendig, um begründete Entscheidungen bei der Auswahl einer geeigneten Technik zu ermöglichen. In dieser Arbeit wird eine Klassifikation basierend auf einer Vereinheitlichung von 23 Techniken eingeführt. Eine engere Betrachtung von 16 strukturellen Techniken liefert eine Subkategorisierung in verbindungs-, metrik-, graph- und begriffsbasierte Techniken. Über den rein qualitativen Vergleich hinaus werden 12 strukturelle Techniken quantitativ beurteilt (alle bis auf begriffsbasierte Techniken). Zu diesem Zweck wird ein Auswerteschema für Komponentenerkennungstechniken vorgestellt, mit dessen Hilfe die Erkennungsqualität hinsichtlich einer manuell ermittelten Menge von Komponenten genau bestimmt werden kann. Unter den bewerteten Techniken befindet sich unsere neue metrikbasierte Technik Similarity Clustering. Bei der Auswertung anhand der von 5 Software-Ingenieuren erkannten Komponenten für vier C-Systeme mit zusammen 136 KLOC befindet sich Similarity Clustering bezüglich seiner Wiederfindungsrate stets unter den besten Techniken; allerdings ist auch eine höhere Anzahl unzuordenbarer Komponenten als bei anderen Techniken zu verzeichnen. Als Resultat ergibt sich insgesamt, dass keine der automatischen Techniken eine ausreichende Erkennungsqualität aufweisen kann. Um diesen Mangel auszugleichen, wird eine halbautomatische Methode eingeführt, die unterstützt wird durch eine Integration der vollautomatischen Techniken als sukzessiv angewandte Analysen mit anschließender Validierung durch den Benutzer. Hierzu werden die Techniken zu inkrementellen Techniken erweitert. Die Resultate der Techniken können mittels Operatoren kombiniert werden, denen die Mengenoperationen Schnitt, Vereinigung und Differenz zugrunde liegen. Eine alternative Art der Integration ist der sogenannte Abstimmungsansatz, bei dem die individuellen Zustimmungen der Techniken zusammengefasst werden.