Parallel Genetic Algorithm for Document Image Compression Optimization

This work proposes a parallel genetic algorithm for compressing scanned document images. A fitness function is designed with Hausdorff distance which determines the terminating condition. The algorithm helps to locate the text lines. A greater compression ratio has achieved with lesser distortion

Entwicklung und experimentelle Regelung eines servopneumatischen räumlichen Mehrachsenprüfstands

In dieser Arbeit wurde ein räumlich bewegter pneumatischer Mehrachsenprüfstand als spezielle mechanische Variante eines Parallelroboters entwickelt, im Labor aufgebaut und in Rechnersimulationen sowie in Laborexperimenten regelungstechnisch untersucht. Für diesen speziellen Parallelroboter MAP-RTS-6 wurden Regelalgorithmen, die mittels moderner Verfahren der linearen und nichtlinearen Regelungstheorie abgeleitet wurden, hinsichtlich ihrer praktischen Anwendbarkeit, Echtzeitfähigkeit und Qualität entwickelt, implementiert und überprüft. Mit diesen Regelalgorithmen ist der MAP-RTS-6 in der Lage, große räumliche Transienten schnell und präzise nachzufahren. Der MAP-RTS-6 wird in erster Linie als räumlicher Bewegungsmanipulator für große nichtlineare Transienten (Translationen und Rotationen), als räumlicher Vibrationsprüfstand für starre und flexible Prüfkörper unterschiedlicher Konfigurationen und als Mechanismus für die Implementierung und experimentelle Überprüfung unterschiedlicher Regelungs- und Identifikationsalgorithmen und Sicherheitskonzepte verwendet. Die Voraussetzung zum Betrieb des Mehrachsenprüfstands für unterschiedliche redundante Antriebskonfigurationen mit sieben und acht Antrieben MAP-RTS-7 und MAP-RTS-8 wurde in dieser Arbeit geschaffen. Dazu zählen die konstruktive Vorbereitung der Prüfstandsmechanik und Pneumatik zum Anschluss weiterer Antriebe, die Vorbereitung zusätzlicher I/O-Schnittstellen zur Prüfstandselektronik und zum Regelungssystem und die Ableitung von Algorithmen zur analytischen Arbeitsraumüberwachung für redundante Antriebskonfigurationen mit sieben und acht Antrieben.

Evaluating the state of the art of parallel programming systems

This paper describes our plans to evaluate the present state of affairs concerning parallel programming and its systems. Three subprojects are proposed: a survey among programmers and scientists, a comparison of parallel programming systems using a standard set of test programs, and a wiki resource for the parallel programming community - the Parawiki. We would like to invite you to participate and turn these subprojects into true community efforts.

Observations on the Publicity and Usage of Parallel Programming Systems and Languages: A Survey Approach

In this publication, we report on an online survey that was carried out among parallel programmers. More than 250 people worldwide have submitted answers to our questions, and their responses are analyzed here. Although not statistically sound, the data we provide give useful insights about which parallel programming systems and languages are known and in actual use. For instance, the collected data indicate that for our survey group MPI and (to a lesser extent) C are the most widely used parallel programming system and language, respectively.

A User-Centric Perspective on Parallel Programming with Focus on OpenMP

The process of developing software that takes advantage of multiple processors is commonly referred to as parallel programming. For various reasons, this process is much harder than the sequential case. For decades, parallel programming has been a problem for a small niche only: engineers working on parallelizing mostly numerical applications in High Performance Computing. This has changed with the advent of multi-core processors in mainstream computer architectures. Parallel programming in our days becomes a problem for a much larger group of developers. The main objective of this thesis was to find ways to make parallel programming easier for them. Different aims were identified in order to reach the objective: research the state of the art of parallel programming today, improve the education of software developers about the topic, and provide programmers with powerful abstractions to make their work easier. To reach these aims, several key steps were taken. To start with, a survey was conducted among parallel programmers to find out about the state of the art. More than 250 people participated, yielding results about the parallel programming systems and languages in use, as well as about common problems with these systems. Furthermore, a study was conducted in university classes on parallel programming. It resulted in a list of frequently made mistakes that were analyzed and used to create a programmers' checklist to avoid them in the future. For programmers' education, an online resource was setup to collect experiences and knowledge in the field of parallel programming - called the Parawiki. Another key step in this direction was the creation of the Thinking Parallel weblog, where more than 50.000 readers to date have read essays on the topic. For the third aim (powerful abstractions), it was decided to concentrate on one parallel programming system: OpenMP. Its ease of use and high level of abstraction were the most important reasons for this decision. Two different research directions were pursued. The first one resulted in a parallel library called AthenaMP. It contains so-called generic components, derived from design patterns for parallel programming. These include functionality to enhance the locks provided by OpenMP, to perform operations on large amounts of data (data-parallel programming), and to enable the implementation of irregular algorithms using task pools. AthenaMP itself serves a triple role: the components are well-documented and can be used directly in programs, it enables developers to study the source code and learn from it, and it is possible for compiler writers to use it as a testing ground for their OpenMP compilers. The second research direction was targeted at changing the OpenMP specification to make the system more powerful. The main contributions here were a proposal to enable thread-cancellation and a proposal to avoid busy waiting. Both were implemented in a research compiler, shown to be useful in example applications, and proposed to the OpenMP Language Committee.

On Parallel Communicating Grammar Systems and Correctness Preserving Restarting Automata

This paper contributes to the study of Freely Rewriting Restarting Automata (FRR-automata) and Parallel Communicating Grammar Systems (PCGS), which both are useful models in computational linguistics. For PCGSs we study two complexity measures called 'generation complexity' and 'distribution complexity', and we prove that a PCGS Pi, for which the generation complexity and the distribution complexity are both bounded by constants, can be transformed into a freely rewriting restarting automaton of a very restricted form. From this characterization it follows that the language L(Pi) generated by Pi is semi-linear, that its characteristic analysis is of polynomial size, and that this analysis can be computed in polynomial time.

Gender and Space in Tehran

Abstract: This dissertation generally concentrates on the relationships between “gender” and “space” in the present time of urban life in capital city of Tehran. “Gender” as a changing social construct, differentiated within societies and through time, studied this time by investigation on “gender attitude” or “gender identity” means attitudes towards “gender” issues regarding Tehran residences. “Space” as a concept integrated from physical and social constituents investigated through focus on “spatial attitude” means attitudes towards using “living spaces” including private space of “house”, semi private semi public space of neighborhood and finally public spaces of the city. “Activities and practices” in space concentrated instead of “physical” space; this perspective to “space” discussed as the most justified implication of “space” in this debate regarding current situations in city of Tehran. Under a systematic approach, the interactions and interconnections between “gender” and “space” as two constituent variables of social organization investigated by focus on the different associations presented between different “gender identities” and their different “spatial identities”; in fact, “spatial identity” manifests “gender identity” and in opposite direction, “spatial identity” influences to construction of “gender identity”. The hypotheses of case study in Tehran defined as followed: • “Gender identity” is reflected on “spatial identity”. Various “gender identities” in Tehran present different perspectives of “space” or they identify “space” by different values. • As “gender identity” internalizes patriarchal oppression, it internalizes associated “spatial” oppression too. • Within the same social class, different “gender identities” related to men and women, present interconnected qualities, compared with “gender identities” related to men or women of different social classes. This situation could be found in the “spatial” perspectives of different groups of men and women too. • Following the upper hypotheses, “spatial” oppression differs among social classes of Tehran living in different parts of this city. This research undertook a qualitative study in Tehran by interviewing with different parents of both young daughter and son regarding their attitudes towards gender issues from one side and activities and behaviors of their children in different spaces from the other side. Results of case study indicated the parallel changes of parents’ attitudes towards “gender” and “spatial” issues; it means strong connection between “gender” and “space”. It revealed association of “equal” spatial attitudes with “open, neutral” gender attitudes, and also the association of “biased, unequal” spatial identities with “conservative patriarchal” gender identities. It was cleared too that this variable concept – gender space - changes by “sex”; mothers comparing fathers presented more equitable notions towards “gender spatial” issues. It changes too by “social class” and “educational level”, that means “gender spatial” identity getting more open equitable among more educated people of middle and upper classes. “Breadwinning status in the family” also presents its effect on the changes of “gender spatial” identity so participant breadwinners in the family expressed relatively more equitable notions comparing householders and housekeepers. And finally, “gender spatial” identity changes through “place” in the city and regarding South – North line of the city. The illustration of changes of “gender spatial” identity from “open” to “conservative” among society indicated not only vertical variation across social classes, furthermore the horizontal changing among each social class. These results also confirmed hypotheses while made precision on the third one regarding variable of sex. More investigations pointed to some inclusive spatial attitudes throughout society penetrated to different groups of “gender identities”, to “opens” as to “conservatives”, also to groups between them, by two opposite features; first kind, conservative biased spatial practices in favor of patriarchal gender relations and the second, progressive neutral actions in favor of equal gender relations. While the major reason for the inclusive conservative practices was referred to the social insecurity for women, the second neutral ones associated to more formal & safer spaces of the city. In conclusion, while both trends are associated deeply with the important issues of “sex” & “body” in patriarchal thoughts, still strong, they are the consequences of the transitional period of social change in macro level, and the challenges involved regarding interactions between social orders, between old system of patriarchy, the traditional biased “gender spatial” relations and the new one of equal relations. The case study drew an inhomogeneous illustration regarding gender spatial aspects of life in Tehran, the opposite groups of “open” and “conservative”, and the large group of “semi open semi conservative” between them. In macro perspective it presents contradicted social groups according their general life styles; they are the manifestations of challenging trends towards tradition and modernity in Iranian society. This illustration while presents unstable social situations, necessitates probing solutions for social integration; exploring the directions could make heterogeneous social groups close in the way they think and the form they live in spaces. Democratic approaches like participatory development planning might be helpful for the city in its way to more solidarity and sustainability regarding its social spatial – gender as well – development, in macro levels of social spatial planning and in micro levels of physical planning, in private space of house and in public spaces of the city.

Evolving Distributed Algorithms with Genetic Programming

Distributed systems are one of the most vital components of the economy. The most prominent example is probably the internet, a constituent element of our knowledge society. During the recent years, the number of novel network types has steadily increased. Amongst others, sensor networks, distributed systems composed of tiny computational devices with scarce resources, have emerged. The further development and heterogeneous connection of such systems imposes new requirements on the software development process. Mobile and wireless networks, for instance, have to organize themselves autonomously and must be able to react to changes in the environment and to failing nodes alike. Researching new approaches for the design of distributed algorithms may lead to methods with which these requirements can be met efficiently. In this thesis, one such method is developed, tested, and discussed in respect of its practical utility. Our new design approach for distributed algorithms is based on Genetic Programming, a member of the family of evolutionary algorithms. Evolutionary algorithms are metaheuristic optimization methods which copy principles from natural evolution. They use a population of solution candidates which they try to refine step by step in order to attain optimal values for predefined objective functions. The synthesis of an algorithm with our approach starts with an analysis step in which the wanted global behavior of the distributed system is specified. From this specification, objective functions are derived which steer a Genetic Programming process where the solution candidates are distributed programs. The objective functions rate how close these programs approximate the goal behavior in multiple randomized network simulations. The evolutionary process step by step selects the most promising solution candidates and modifies and combines them with mutation and crossover operators. This way, a description of the global behavior of a distributed system is translated automatically to programs which, if executed locally on the nodes of the system, exhibit this behavior. In our work, we test six different ways for representing distributed programs, comprising adaptations and extensions of well-known Genetic Programming methods (SGP, eSGP, and LGP), one bio-inspired approach (Fraglets), and two new program representations called Rule-based Genetic Programming (RBGP, eRBGP) designed by us. We breed programs in these representations for three well-known example problems in distributed systems: election algorithms, the distributed mutual exclusion at a critical section, and the distributed computation of the greatest common divisor of a set of numbers. Synthesizing distributed programs the evolutionary way does not necessarily lead to the envisaged results. In a detailed analysis, we discuss the problematic features which make this form of Genetic Programming particularly hard. The two Rule-based Genetic Programming approaches have been developed especially in order to mitigate these difficulties. In our experiments, at least one of them (eRBGP) turned out to be a very efficient approach and in most cases, was superior to the other representations.

Generic Finite Element Model for Mechanically Consistent Scaling of Composite Beam-to-column Joint with Welded Connection

To study the behaviour of beam-to-column composite connection more sophisticated finite element models is required, since component model has some severe limitations. In this research a generic finite element model for composite beam-to-column joint with welded connections is developed using current state of the art local modelling. Applying mechanically consistent scaling method, it can provide the constitutive relationship for a plane rectangular macro element with beam-type boundaries. Then, this defined macro element, which preserves local behaviour and allows for the transfer of five independent states between local and global models, can be implemented in high-accuracy frame analysis with the possibility of limit state checks. In order that macro element for scaling method can be used in practical manner, a generic geometry program as a new idea proposed in this study is also developed for this finite element model. With generic programming a set of global geometric variables can be input to generate a specific instance of the connection without much effort. The proposed finite element model generated by this generic programming is validated against testing results from University of Kaiserslautern. Finally, two illustrative examples for applying this macro element approach are presented. In the first example how to obtain the constitutive relationships of macro element is demonstrated. With certain assumptions for typical composite frame the constitutive relationships can be represented by bilinear laws for the macro bending and shear states that are then coupled by a two-dimensional surface law with yield and failure surfaces. In second example a scaling concept that combines sophisticated local models with a frame analysis using a macro element approach is presented as a practical application of this numerical model.

Systems of Parallel Communicating Restarting Automata

In der vorliegenden Dissertation werden Systeme von parallel arbeitenden und miteinander kommunizierenden Restart-Automaten (engl.: systems of parallel communicating restarting automata; abgekürzt PCRA-Systeme) vorgestellt und untersucht. Dabei werden zwei bekannte Konzepte aus den Bereichen Formale Sprachen und Automatentheorie miteinander vescrknüpft: das Modell der Restart-Automaten und die sogenannten PC-Systeme (systems of parallel communicating components). Ein PCRA-System besteht aus endlich vielen Restart-Automaten, welche einerseits parallel und unabhängig voneinander lokale Berechnungen durchführen und andererseits miteinander kommunizieren dürfen. Die Kommunikation erfolgt dabei durch ein festgelegtes Kommunikationsprotokoll, das mithilfe von speziellen Kommunikationszuständen realisiert wird. Ein wesentliches Merkmal hinsichtlich der Kommunikationsstruktur in Systemen von miteinander kooperierenden Komponenten ist, ob die Kommunikation zentralisiert oder nichtzentralisiert erfolgt. Während in einer nichtzentralisierten Kommunikationsstruktur jede Komponente mit jeder anderen Komponente kommunizieren darf, findet jegliche Kommunikation innerhalb einer zentralisierten Kommunikationsstruktur ausschließlich mit einer ausgewählten Master-Komponente statt. Eines der wichtigsten Resultate dieser Arbeit zeigt, dass zentralisierte Systeme und nichtzentralisierte Systeme die gleiche Berechnungsstärke besitzen (das ist im Allgemeinen bei PC-Systemen nicht so). Darüber hinaus bewirkt auch die Verwendung von Multicast- oder Broadcast-Kommunikationsansätzen neben Punkt-zu-Punkt-Kommunikationen keine Erhöhung der Berechnungsstärke. Desweiteren wird die Ausdrucksstärke von PCRA-Systemen untersucht und mit der von PC-Systemen von endlichen Automaten und mit der von Mehrkopfautomaten verglichen. PC-Systeme von endlichen Automaten besitzen bekanntermaßen die gleiche Ausdrucksstärke wie Einwegmehrkopfautomaten und bilden eine untere Schranke für die Ausdrucksstärke von PCRA-Systemen mit Einwegkomponenten. Tatsächlich sind PCRA-Systeme auch dann stärker als PC-Systeme von endlichen Automaten, wenn die Komponenten für sich genommen die gleiche Ausdrucksstärke besitzen, also die regulären Sprachen charakterisieren. Für PCRA-Systeme mit Zweiwegekomponenten werden als untere Schranke die Sprachklassen der Zweiwegemehrkopfautomaten im deterministischen und im nichtdeterministischen Fall gezeigt, welche wiederum den bekannten Komplexitätsklassen L (deterministisch logarithmischer Platz) und NL (nichtdeterministisch logarithmischer Platz) entsprechen. Als obere Schranke wird die Klasse der kontextsensitiven Sprachen gezeigt. Außerdem werden Erweiterungen von Restart-Automaten betrachtet (nonforgetting-Eigenschaft, shrinking-Eigenschaft), welche bei einzelnen Komponenten eine Erhöhung der Berechnungsstärke bewirken, in Systemen jedoch deren Stärke nicht erhöhen. Die von PCRA-Systemen charakterisierten Sprachklassen sind unter diversen Sprachoperationen abgeschlossen und einige Sprachklassen sind sogar abstrakte Sprachfamilien (sogenannte AFL's). Abschließend werden für PCRA-Systeme spezifische Probleme auf ihre Entscheidbarkeit hin untersucht. Es wird gezeigt, dass Leerheit, Universalität, Inklusion, Gleichheit und Endlichkeit bereits für Systeme mit zwei Restart-Automaten des schwächsten Typs nicht semientscheidbar sind. Für das Wortproblem wird gezeigt, dass es im deterministischen Fall in quadratischer Zeit und im nichtdeterministischen Fall in exponentieller Zeit entscheidbar ist.

On Connection, Linearization and Duplication Coefficients of Classical Orthogonal Polynomials

In this work, we have mainly achieved the following: 1. we provide a review of the main methods used for the computation of the connection and linearization coefficients between orthogonal polynomials of a continuous variable, moreover using a new approach, the duplication problem of these polynomial families is solved; 2. we review the main methods used for the computation of the connection and linearization coefficients of orthogonal polynomials of a discrete variable, we solve the duplication and linearization problem of all orthogonal polynomials of a discrete variable; 3. we propose a method to generate the connection, linearization and duplication coefficients for q-orthogonal polynomials; 4. we propose a unified method to obtain these coefficients in a generic way for orthogonal polynomials on quadratic and q-quadratic lattices. Our algorithmic approach to compute linearization, connection and duplication coefficients is based on the one used by Koepf and Schmersau and on the NaViMa algorithm. Our main technique is to use explicit formulas for structural identities of classical orthogonal polynomial systems. We find our results by an application of computer algebra. The major algorithmic tools for our development are Zeilberger’s algorithm, q-Zeilberger’s algorithm, the Petkovšek-van-Hoeij algorithm, the q-Petkovšek-van-Hoeij algorithm, and Algorithm 2.2, p. 20 of Koepf's book "Hypergeometric Summation" and it q-analogue.

An O(N) Algorithm for Three-Dimensional N-Body Simulations

We develop an algorithm that computes the gravitational potentials and forces on N point-masses interacting in three-dimensional space. The algorithm, based on analytical techniques developed by Rokhlin and Greengard, runs in order N time. In contrast to other fast N-body methods such as tree codes, which only approximate the interaction potentials and forces, this method is exact ?? computes the potentials and forces to within any prespecified tolerance up to machine precision. We present an implementation of the algorithm for a sequential machine. We numerically verify the algorithm, and compare its speed with that of an O(N2) direct force computation. We also describe a parallel version of the algorithm that runs on the Connection Machine in order 0(logN) time. We compare experimental results with those of the sequential implementation and discuss how to minimize communication overhead on the parallel machine.

Pi: A Parallel Architecture Interface for Multi-Model Execution

This thesis defines Pi, a parallel architecture interface that separates model and machine issues, allowing them to be addressed independently. This provides greater flexibility for both the model and machine builder. Pi addresses a set of common parallel model requirements including low latency communication, fast task switching, low cost synchronization, efficient storage management, the ability to exploit locality, and efficient support for sequential code. Since Pi provides generic parallel operations, it can efficiently support many parallel programming models including hybrids of existing models. Pi also forms a basis of comparison for architectural components.

Parallel Methods for Synthesizing Whole-Hand Grasps from Generalized Prototypes

This report addresses the problem of acquiring objects using articulated robotic hands. Standard grasps are used to make the problem tractable, and a technique is developed for generalizing these standard grasps to increase their flexibility to variations in the problem geometry. A generalized grasp description is applied to a new problem situation using a parallel search through hand configuration space, and the result of this operation is a global overview of the space of good solutions. The techniques presented in this report have been implemented, and the results are verified using the Salisbury three-finger robotic hand.

Thread Scheduling Mechanisms for Multiple-Context Parallel Processors

Scheduling tasks to efficiently use the available processor resources is crucial to minimizing the runtime of applications on shared-memory parallel processors. One factor that contributes to poor processor utilization is the idle time caused by long latency operations, such as remote memory references or processor synchronization operations. One way of tolerating this latency is to use a processor with multiple hardware contexts that can rapidly switch to executing another thread of computation whenever a long latency operation occurs, thus increasing processor utilization by overlapping computation with communication. Although multiple contexts are effective for tolerating latency, this effectiveness can be limited by memory and network bandwidth, by cache interference effects among the multiple contexts, and by critical tasks sharing processor resources with less critical tasks. This thesis presents techniques that increase the effectiveness of multiple contexts by intelligently scheduling threads to make more efficient use of processor pipeline, bandwidth, and cache resources. This thesis proposes thread prioritization as a fundamental mechanism for directing the thread schedule on a multiple-context processor. A priority is assigned to each thread either statically or dynamically and is used by the thread scheduler to decide which threads to load in the contexts, and to decide which context to switch to on a context switch. We develop a multiple-context model that integrates both cache and network effects, and shows how thread prioritization can both maintain high processor utilization, and limit increases in critical path runtime caused by multithreading. The model also shows that in order to be effective in bandwidth limited applications, thread prioritization must be extended to prioritize memory requests. We show how simple hardware can prioritize the running of threads in the multiple contexts, and the issuing of requests to both the local memory and the network. Simulation experiments show how thread prioritization is used in a variety of applications. Thread prioritization can improve the performance of synchronization primitives by minimizing the number of processor cycles wasted in spinning and devoting more cycles to critical threads. Thread prioritization can be used in combination with other techniques to improve cache performance and minimize cache interference between different working sets in the cache. For applications that are critical path limited, thread prioritization can improve performance by allowing processor resources to be devoted preferentially to critical threads. These experimental results show that thread prioritization is a mechanism that can be used to implement a wide range of scheduling policies.