CDAC / The introduction of languages like High Performance Fortran (HPF) which allow the programmer to indicate how the arrays used in the program have to be distributed across the local memories of a multi-computer has not completely unburdened the parallel programmer from the intricacies of these architectures. In order to tap the full potential of these architectures, the compiler has to perform this crucial task of data partitioning automatically. This would not only unburden the programmer but would make the programs more efficient since the compiler can be made more intelligent to take care of the architectural nuances. The topic of this thesis namely the automatic data partitioning deals with finding the best data partition for the various arrays used in the entire program in such a way that the cost of execution of the entire program is minimized. The compiler could resort to runtime redistribution of the arrays at various points in the program if found profitable. Several aspects of this problem have been proven to be NP-complete. Other researchers have suggested heuristic solutions to solve this problem. In this thesis we propose a genetic algorithm namely the Hierarchical Genetic Search algorithm to solve this problem.

Automatic Global Data Partitioning for Distributed Memory Machines (DMMs) is a difficult problem. Distributed memory machines are scalable, but since the memory is distributed across processors, the scheme of placement of data (arrays) onto local memories of different processors become crucial since any communication between processors for non-local data access is an order of magnitude costlier than access to local memory. Researchers have given varied solutions to this problem, most of which work for uniform dependences in loops and they suggest HPF-like distributions only. For non-uniform dependences the loop was made to run sequentially. In this work, we present a partitioning strategy called Hyperplane Partitioning which works well with loops with non-uniform dependences also. In this method of partitioning, the iteration space is partitioned into as many number of partitions as there are number of logical processors, in such a way that the overall inter-processor communication will be minimum. The idea is to localize as many as dependences as possible so that overall communication both beacuse of non-local data as well as inter-processor synchronizations are reduced. These partitions are then induced into data spaces of the arrays referenced in the loop. Each processor then runs its part of iteration space keeping the data partition that it owns locally. Any non-local data access is implemented by inter-processor communication at run-time.The Hyperplane Partitioning is also extended to a sequence of loops. This is done by first finding Best Local Distribution (BLD) for every loop first and then finding the best way of grouping different adjacent loops (just for finding the data partition) which gives best global data partition. This sequence of distributions/redistributions is found by constructing a data structure called Data Distribution Tree (DDT) and finding the least cost path from the source to any of the leaf nodes in the DDT. The costs for the edges come from the communication cost incurred while running a loop with a particular distribution and redistribution to suit the requirement at the next loop. For this a communication cost estimator is developed which works well for fewer dimensions. To handle complete programs we use some heuristic to find the best global distribution for the entire program.Some optimizations like message optimization to reduce the number of messages sent across processors, time optimization which is done by uniform scheduling across processors, and space optimization to keep only the part of array space that any processor owns onto its local memory, are studied. Hyperplane Partitioning is also implemented using an algorithm for synchronization to handle non-local memory access as well as obeying data dependence constraints. The algorithm is also proved to be correct. The target machine is IBM-SP2 using PVM for the message passing library. The performance of the tool on some standard benchmarks (ADI and RHS) and also on some programs designed by us to show the specific merits of the tool. The results show that the loops which have non-uniform dependences also can be run on DMM with good speed-ups.

ON PRESENTE LES PRINCIPAUX OUTILS QUI PERMETTENT DE SPECIFIER ET D'IMPLEMENTER LES MECANISMES DE SYNCHRONISATION DANS UN SYSTEME MONOPROCESSEUR PUIS MULTIPROCESSEUR. ON DEFINIT ET ON MONTRE LES REGLES D'EVOLUTION DES RESEAUX DE PETRI ET ON DETAILLE LES DIVERSES METHODES D'ANALYSE QU'ILS AUTORISENT. ON PROPOSE UN MODELE DERIVE APPELE RESEAUX DE PETRI A JETONS INDIVIDUALISES. ON DECRIT UN ALGORITHME DE SYNCHRONISATION ET ON PROPOSE UNE MISE EN OEUVRE DE CET ALGORITHME A PARTIR DES RESEAUX DE PETRI A JETONS INDIVIDUALISES

Made available in DSpace on 2014-06-11T19:24:04Z (GMT). No. of bitstreams: 0 Previous issue date: 2012-08-13Bitstream added on 2014-06-13T19:30:35Z : No. of bitstreams: 1 cardoso_vl_me_bauru.pdf: 1164612 bytes, checksum: ea073a5e701ce3e72b73494cedeafeda (MD5) / Fundação de Amparo à Pesquisa do Estado de São Paulo (FAPESP) / Esta dissertação analisa as políticas de implantação da multiprogramação pela TV Cultura, emissora sob responsabilidade da Fundação Padre Anchieta. A análise evidencia a implantação da televisão digital no Brasil e contempla as políticas públicas que regulamentam o funcionamento da televisão digital da televisão pública e da televisão educativa. A dissertação foca nos processos políticos que envolvem a criação e a implantação dos canais de multiprogramação da emissora: o Univesp TV e o MultiCultura. Ambos estão em funcionamento por meio de autorização especial e operam atualmente em caráter científico e experimental. Como resultado, identifica-se a existência de jogos de poder e de interesses políticos e financeiros no processo de implantação, além da fragilidade legal envolvendo a multiprogramação. Mesmo limitada à União, a partir dos acontecimentos ligados a TV Cultura, constata-se, por meio da legislação vigente, que a tecnologia pode ser praticada em caráter científico e experimental por qualquer concessionária que tenha a autorização do Ministério das Comunicações e da Anatel - Agência Nacional de Telecomunicações. Aponta-se ainda a relevância da tecnologia como instrumento de comtemplação dos princípios constitucionais de democratização da comunicação. A dissertação é um estudo exploratório, bibliográfico e documental sobre este significativo momento de transição e experimentação que ocorre na televisão brasileira. A análise baseia-se na visão da Economia Política da Comunicação utilizando a pesquisa qualitativa como metodologia de trabalho / The present dissertation analyses the political deployment of multiprogramming by TV Cultura, broadcaster under the resposability of the Padre Anchieta Foundation. The analysis highlights the deployment of digital TV in Brazil, and contemplates the public policies that regulate the operation of digital television, of public television and of educational television. The dissertation focuses on the political processes that involve the creation and the implementation of the multiprogramming channels by the broadcaster: Univesp TV and MultiCultura. Both are running by means of a special authorization and currently operate in a scientific and experimental way. As a result, it identifies the existence of games of power and of political and financial interest in the process of implementation, besides the legal fragility involving multiprogramming. Even though limited to the Union, it is possible to assert, from the events connected to RV Cultura and from the current legislation, that the technology can be practiced in a scientific and experimental way by any concessionary that has the authorization of the Ministry of Communications and of Anatel - the National Telecommunications Agency. Furthermore, it indicates the relevance of the technology as means of contemplating the constitucional principles of democratization of communication. The dissertation is an exploratory, bibliographic and documentary study on this significant time of transition and experimentation that is occurring in the Brazilian television. The analysis is based on the perspective of the Political Economy of Communication and uses the qualitative research as its work method