Universität Stuttgart
Permanent URI for this communityhttps://elib.uni-stuttgart.de/handle/11682/1
Browse
Search Results
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 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 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 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.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 Themenspezifische Informationssuche im Internet mit Hilfe mobiler Programme(2000) Theilmann, Wolfgang; Rothermel, Kurt (Prof. Dr. rer. nat.)Das Forschungsgebiet der Informationssuche (Information Retrieval) wird durch das Aufkommen des Internets bzw. des World Wide Web mit völlig neuen Herausforderungen konfrontiert. Im Gegensatz zu herkömmlichen Datenbeständen zeichnet sich das Internet durch seinen immensen Umfang, eine hohe Dynamik, die Heterogenität seiner Inhalte sowie die Verteilung über Rechner auf der ganzen Erde aus. Um auch in diesem Informationsraum präzise, effizient und umfassend nach Informationen suchen zu können, wird in dieser Arbeit ein Konzept zur Spezialisierung von Suchmaschinen auf einzelne Themengebiete vorgeschlagen. Solche Suchmaschinen erkennen die für sie relevanten Dokumente anhand einer speziellen Filterfunktion und können ihren Benutzern eine themenspezifische Benutzungsschnittstelle und Suchfunktionalität bieten. Um die für eine spezialisierte Suchmaschine relevanten Dokumente effizient zu lokalisieren, wird die Technologie der mobilen Programme eingesetzt. Anstatt alle zu untersuchenden Dokumente zur Suchmaschine zu übertragen, werden mobile Filterprogramme zu den Datenbeständen gesandt, untersuchen diese 'vor Ort' und liefern lediglich die relevanten Dokumente zurück. Es werden Verfahren vorgestellt, mit denen die Aussendung der mobilen Programme so koordiniert werden kann, dass die resultierenden Kommunikationskosten minimiert werden. Da von diesen Aussendungsverfahren Kenntnisse über die netzwerktechnische Entfernung zwischen den beteiligten Rechnern benötigt werden, wird zudem ein Ansatz vorgestellt, der die Schätzung beliebiger Netzwerkdistanzen im Internet auf skalierbare und effiziente Weise ermöglicht. Die Tragfähigkeit der Konzepte zur Schätzung von Netzwerkdistanzen und zur Aussendung mobiler Programme wird anhand umfangreicher Messungen evaluiert. Zudem wird in einer Fallstudie der Nutzen der themenspezifischen Suchmaschinen sowie der in ihrem Kontext erfolgende Einsatz mobiler Filterprogramme analysiert.