A programação de tarefas em linhas de produção nas empresas sempre foi e continua sendo um elemento fundamental para o sucesso das organizações em um mercado tão globalizado e competitivo. A melhor utilização dos recursos instalados através da melhor alocação das tarefas gerará melhores resultados para a organização. Entende-se pela melhor utilização dos recursos a redução do tempo total de finalização das tarefas (makespan) sem prejudicar o atendimento da data de entrega. Aplica-se esta idéia para as indústrias de um modo geral, que tenham linhas de produção, podendo citar a indústria calçadista, foco neste trabalho, as indústrias de massas, biscoitos e balas, entre outras. Na literatura especializada, esta programação é conhecida como sequenciamento de tarefas em processadores. Neste trabalho aplicado junto a indústria calçadista, foca-se em uma área mais específica: o sequenciamento de tarefas em processadores paralelos. Os problemas de sequenciamento se caracterizam pela grande exigência computacional para a resolução com algoritmos de otimização. Isto remete a utilização de heurísticas para a resolução destes problemas. Neste trabalho explora-se a Meta-Heurística Busca Tabu, que se apresentou com resultados muito bons em relação ao ótimo e em relação ao trabalhador humano. / The jobs scheduling in processor lines in the companies was always, and continues being, a fundamental element to the organization’s success in a very globalized and competitive market. The best use of the installed resources, through the best distribution of the jobs will generate better results for the organization. The best utilization of the resources means the reduction of the makespan without prejudicing the due-date. This idea is applied to all industries in general, that have processor lines, for example the shoes factories, focused in this research, pasta, cookies and sugar balls factories, beyond others. In the specialized literature this subject is know as job scheduling. This researh is applyed to a shoes factory is focused on more specific area: the job scheduling in parallel machines. The scheduling problems are characterized on its computational difficulty using optimization algoritms. That is the reason why we used heuristics to solve these problems. In this research we explore the Meta-Heuristic Tabu Search, wich showed very good results comparing to the optimun and comparing to the human worker.

A programação de tarefas em linhas de produção nas empresas sempre foi e continua sendo um elemento fundamental para o sucesso das organizações em um mercado tão globalizado e competitivo. A melhor utilização dos recursos instalados através da melhor alocação das tarefas gerará melhores resultados para a organização. Entende-se pela melhor utilização dos recursos a redução do tempo total de finalização das tarefas (makespan) sem prejudicar o atendimento da data de entrega. Aplica-se esta idéia para as indústrias de um modo geral, que tenham linhas de produção, podendo citar a indústria calçadista, foco neste trabalho, as indústrias de massas, biscoitos e balas, entre outras. Na literatura especializada, esta programação é conhecida como sequenciamento de tarefas em processadores. Neste trabalho aplicado junto a indústria calçadista, foca-se em uma área mais específica: o sequenciamento de tarefas em processadores paralelos. Os problemas de sequenciamento se caracterizam pela grande exigência computacional para a resolução com algoritmos de otimização. Isto remete a utilização de heurísticas para a resolução destes problemas. Neste trabalho explora-se a Meta-Heurística Busca Tabu, que se apresentou com resultados muito bons em relação ao ótimo e em relação ao trabalhador humano. / The jobs scheduling in processor lines in the companies was always, and continues being, a fundamental element to the organization’s success in a very globalized and competitive market. The best use of the installed resources, through the best distribution of the jobs will generate better results for the organization. The best utilization of the resources means the reduction of the makespan without prejudicing the due-date. This idea is applied to all industries in general, that have processor lines, for example the shoes factories, focused in this research, pasta, cookies and sugar balls factories, beyond others. In the specialized literature this subject is know as job scheduling. This researh is applyed to a shoes factory is focused on more specific area: the job scheduling in parallel machines. The scheduling problems are characterized on its computational difficulty using optimization algoritms. That is the reason why we used heuristics to solve these problems. In this research we explore the Meta-Heuristic Tabu Search, wich showed very good results comparing to the optimun and comparing to the human worker.

A programação de tarefas em linhas de produção nas empresas sempre foi e continua sendo um elemento fundamental para o sucesso das organizações em um mercado tão globalizado e competitivo. A melhor utilização dos recursos instalados através da melhor alocação das tarefas gerará melhores resultados para a organização. Entende-se pela melhor utilização dos recursos a redução do tempo total de finalização das tarefas (makespan) sem prejudicar o atendimento da data de entrega. Aplica-se esta idéia para as indústrias de um modo geral, que tenham linhas de produção, podendo citar a indústria calçadista, foco neste trabalho, as indústrias de massas, biscoitos e balas, entre outras. Na literatura especializada, esta programação é conhecida como sequenciamento de tarefas em processadores. Neste trabalho aplicado junto a indústria calçadista, foca-se em uma área mais específica: o sequenciamento de tarefas em processadores paralelos. Os problemas de sequenciamento se caracterizam pela grande exigência computacional para a resolução com algoritmos de otimização. Isto remete a utilização de heurísticas para a resolução destes problemas. Neste trabalho explora-se a Meta-Heurística Busca Tabu, que se apresentou com resultados muito bons em relação ao ótimo e em relação ao trabalhador humano. / The jobs scheduling in processor lines in the companies was always, and continues being, a fundamental element to the organization’s success in a very globalized and competitive market. The best use of the installed resources, through the best distribution of the jobs will generate better results for the organization. The best utilization of the resources means the reduction of the makespan without prejudicing the due-date. This idea is applied to all industries in general, that have processor lines, for example the shoes factories, focused in this research, pasta, cookies and sugar balls factories, beyond others. In the specialized literature this subject is know as job scheduling. This researh is applyed to a shoes factory is focused on more specific area: the job scheduling in parallel machines. The scheduling problems are characterized on its computational difficulty using optimization algoritms. That is the reason why we used heuristics to solve these problems. In this research we explore the Meta-Heuristic Tabu Search, wich showed very good results comparing to the optimun and comparing to the human worker.

The thesis deals with planning and scheduling of production in the food industry. The theoretical part is concerned with the formulation and structure of the task scheduling and analyses the flow shop in the detail, for which a real application for an unnamed company has been created. It also briefly describes the technical specifications of production, which are crucial for the practical part. The practical part deals with the formulation of a mathematical model. The optimal solution is obtained using the optimization program MPL for Windows. Mathematical model includes variables that solves serial and parallel processors and try to capture as most exact as possible manufacturing processes with the technical specifications for a particular enterprise. The criterion for optimization is to minimize the cost in terms of the selected technology of production.

No description available.

Parallel computing has recently appeared has an alternative approach to increase computing performance. In the world of engineering and scientific computing the efficient use of parallel computers is dependent on the availability of methodologies capable of exploiting the new computing environment. The research presented here focused on a modeling approach, known as cellular automata (CA), which is characterized by a high degree of parallelism and is thus well suited to implementation on parallel processors. The inherent degree of parallelism also exhibited by the random-walk particle method provided a suitable basis for the development of a CA water quality model. The random-walk particle method was successfully represented using an approach based on CA. The CA approach requires the definition of transition rules, with each rule representing a water quality process. The basic water quality processes of interest in this research were advection, dispersion, and first-order decay. Due to the discrete nature of CA, the rule for advection introduces considerable numerical dispersion. However, the magnitude of this numerical dispersion can be minimized by proper selection of model parameters, namely the size of the cells and the time step. Similarly, the rule for dispersion is also affected by numerical dispersion. But, contrary to advection, a procedure was developed that eliminates significant numerical dispersion associated with the dispersion rule. For first-order decay a rule was derived which describes the decay process without the limitations of a similar approach previously reported in the literature. The rules developed for advection, dispersion, and decay, due to their independence, are well suited to implementation using a time-splitting approach. Through validation of the CA methodology as an integrated water quality model, the methodology was shown to adequately simulate one and two-dimensional, single and multiple constituent, steady state and transient, and spatially invariant and variant systems. The CA results show a good agreement with corresponding results for differential equation based models. The CA model was found to be simpler to understand and implement than the traditional numerical models. The CA model was easily implemented on a MIMD distributed memory parallel computer (Intel Paragon). However, poor performance was obtained. / Ph. D.

MATLAB is an array language, initially popular for rapid prototyping, but is now being in-creasingly used to develop production code for numerical and scientific applications. Typical MATLAB programs have abundant data parallelism. These programs also have control flow dominated scalar regions that have an impact on the program’s execution time. Today’s com-puter systems have tremendous computing power in the form of traditional CPU cores and also throughput-oriented accelerators such as graphics processing units (GPUs). Thus, an approach that maps the control flow dominated regions of a MATLAB program to the CPU and the data parallel regions to the GPU can significantly improve program performance. In this work, we present the design and implementation of MEGHA, a compiler that auto-matically compiles MATLAB programs to enable synergistic execution on heterogeneous pro-cessors. Our solution is fully automated and does not require programmer input for identifying data parallel regions. Our compiler identifies data parallel regions of the program and com-poses them into kernels. The kernel composition step eliminates a number of intermediate arrays which are otherwise required and also reduces the size of the scheduling and mapping problem the compiler needs to solve subsequently. The problem of combining statements into kernels is formulated as a constrained graph clustering problem. Heuristics are presented to map identified kernels to either the CPU or GPU so that kernel execution on the CPU and the GPU happens synergistically, and the amount of data transfer needed is minimized. A heuristic technique to ensure that memory accesses on the CPU exploit locality and those on the GPU are coalesced is also presented. In order to ensure that data transfers required for dependences across basic blocks are performed, we propose a data flow analysis step and an edge-splitting strategy. Thus our compiler automatically handles kernel composition, mapping of kernels to CPU and GPU, scheduling and insertion of required data transfers. Additionally, we address the problem of identifying what variables can coexist in GPU memory simultaneously under the GPU memory constraints. We formulate this problem as that of identifying maximal cliques in an interference graph. We approximate the interference graph using an interval graph and develop an efficient algorithm to solve the problem. Furthermore, we present two program transformations that optimize memory accesses on the GPU using the software managed scratchpad memory available in GPUs. We have prototyped the proposed compiler using the Octave system. Our experiments using this implementation show a geometric mean speedup of 12X on the GeForce 8800 GTS and 29.2X on the Tesla S1070 over baseline MATLAB execution for data parallel benchmarks. Experiments also reveal that our method provides up to 10X speedup over hand written GPUmat versions of the benchmarks. Our method also provides a speedup of 5.3X on the GeForce 8800 GTS and 13.8X on the Tesla S1070 compared to compiled MATLAB code running on the CPU.

Thesis (PhD (Electrical and Electronic Engineering))--University of Stellenbosch, 2011. / ENGLISH ABSTRACT: This work considers the acceleration of matrix-based computational electromagnetic (CEM) techniques using graphics processing units (GPUs). These massively parallel processors have gained much support since late 2006, with software tools such as CUDA and OpenCL greatly simplifying the process of harnessing the computational power of these devices. As with any advances in computation, the use of these devices enables the modelling of more complex problems, which in turn should give rise to better solutions to a number of global challenges faced at present. For the purpose of this dissertation, CUDA is used in an investigation of the acceleration of two methods in CEM that are used to tackle a variety of problems. The first of these is the Method of Moments (MOM) which is typically used to model radiation and scattering problems, with the latter begin considered here. For the CUDA acceleration of the MOM presented here, the assembly and subsequent solution of the matrix equation associated with the method are considered. This is done for both single and double precision oating point matrices. For the solution of the matrix equation, general dense linear algebra techniques are used, which allow for the use of a vast expanse of existing knowledge on the subject. This also means that implementations developed here along with the results presented are immediately applicable to the same wide array of applications where these methods are employed. Both the assembly and solution of the matrix equation implementations presented result in signi cant speedups over multi-core CPU implementations, with speedups of up to 300x and 10x, respectively, being measured. The implementations presented also overcome one of the major limitations in the use of GPUs as accelerators (that of limited memory capacity) with problems up to 16 times larger than would normally be possible being solved. The second matrix-based technique considered is the Finite Element Method (FEM), which allows for the accurate modelling of complex geometric structures including non-uniform dielectric and magnetic properties of materials, and is particularly well suited to handling bounded structures such as waveguide. In this work the CUDA acceleration of the cutoff and dispersion analysis of three waveguide configurations is presented. The modelling of these problems using an open-source software package, FEniCS, is also discussed. Once again, the problem can be approached from a linear algebra perspective, with the formulation in this case resulting in a generalised eigenvalue (GEV) problem. For the problems considered, a total solution speedup of up to 7x is measured for the solution of the generalised eigenvalue problem, with up to 22x being attained for the solution of the standard eigenvalue problem that forms part of the GEV problem. / AFRIKAANSE OPSOMMING: In hierdie werkstuk word die versnelling van matriksmetodes in numeriese elektromagnetika (NEM) deur die gebruik van grafiese verwerkingseenhede (GVEe) oorweeg. Die gebruik van hierdie verwerkingseenhede is aansienlik vergemaklik in 2006 deur sagteware pakette soos CUDA en OpenCL. Hierdie toestelle, soos ander verbeterings in verwerkings vermoe, maak dit moontlik om meer komplekse probleme op te los. Hierdie stel wetenskaplikes weer in staat om globale uitdagings beter aan te pak. In hierdie proefskrif word CUDA gebruik om ondersoek in te stel na die versnelling van twee metodes in NEM, naamlik die Moment Metode (MOM) en die Eindige Element Metode (EEM). Die MOM word tipies gebruik om stralings- en weerkaatsingsprobleme op te los. Hier word slegs na die weerkaatsingsprobleme gekyk. CUDA word gebruik om die opstel van die MOM matriks en ook die daaropvolgende oplossing van die matriksvergelyking wat met die metode gepaard gaan te bespoedig. Algemene digte lineere algebra tegnieke word benut om die matriksvergelykings op te los. Dit stel die magdom bestaande kennis in die vagebied beskikbaar vir die oplossing, en gee ook aanleiding daartoe dat enige implementasies wat ontwikkel word en resultate wat verkry word ook betrekking het tot 'n wye verskeidenheid probleme wat die lineere algebra metodes gebruik. Daar is gevind dat beide die opstelling van die matriks en die oplossing van die matriksvergelyking aansienlik vinniger is as veelverwerker SVE implementasies. 'n Verselling van tot 300x en 10x onderkeidelik is gemeet vir die opstel en oplos fases. Die hoeveelheid geheue beskikbaar tot die GVE is een van die belangrike beperkinge vir die gebruik van GVEe vir groot probleme. Hierdie beperking word hierin oorkom en probleme wat selfs 16 keer groter is as die GVE se beskikbare geheue word geakkommodeer en suksesvol opgelos. Die Eindige Element Metode word op sy beurt gebruik om komplekse geometriee asook nieuniforme materiaaleienskappe te modelleer. Die EEM is ook baie geskik om begrensde strukture soos golfgeleiers te hanteer. Hier word CUDA gebruik of om die afsny- en dispersieanalise van drie gol eierkonfigurasies te versnel. Die implementasie van hierdie probleme word gedoen deur 'n versameling oopbronkode wat bekend staan as FEniCS, wat ook hierin bespreek word. Die probleme wat ontstaan in die EEM kan weereens vanaf 'n lineere algebra uitganspunt benader word. In hierdie geval lei die formulering tot 'n algemene eiewaardeprobleem. Vir die gol eier probleme wat ondersoek word is gevind dat die algemene eiewaardeprobleem met tot 7x versnel word. Die standaard eiewaardeprobleem wat 'n stap is in die oplossing van die algemene eiewaardeprobleem is met tot 22x versnel.

Massively Parallel Processor systems provide the required computational power to solve most large scale High Performance Computing applications. Machines with physically distributed memory allow a cost-effective way to achieve this performance, however, these systems are very diffcult to program and tune. In a distributed-memory organization each processor has direct access to its local memory, and indirect access to the remote memories of other processors. But the cost of accessing a local memory location can be more than one order of magnitude faster than accessing a remote memory location. In these systems, the choice of a good data distribution strategy can dramatically improve performance, although different parts of the data distribution problem have been proved to be NP-complete.The selection of an optimal data placement depends on the program structure, the program's data sizes, the compiler capabilities, and some characteristics of the target machine. In addition, there is often a trade-off between minimizing interprocessor data movement and load balancing on processors. Automatic data distribution tools can assist the programmer in the selection of a good data layout strategy. These use to be source-to-source tools which annotate the original program with data distribution directives.Crucial aspects such as data movement, parallelism, and load balance have to be taken into consideration in a unified way to efficiently solve the data distribution problem.In this thesis a framework for automatic data distribution is presented, in the context of a parallelizing environment for massive parallel processor (MPP) systems. The applications considered for parallelization are usually regular problems, in which data structures are dense arrays. The data mapping strategy generated is optimal for a given problem size and target MPP architecture, according to our current cost and compilation model.A single data structure, named Communication-Parallelism Graph (CPG), that holds symbolic information related to data movement and parallelism inherent in the whole program, is the core of our approach. This data structure allows the estimation of the data movement and parallelism effects of any data distribution strategy supported by our model. Assuming that some program characteristics have been obtained by profiling and that some specific target machine features have been provided, the symbolic information included in the CPG can be replaced by constant values expressed in seconds representing data movement time overhead and saving time due to parallelization. The CPG is then used to model a minimal path problem which is solved by a general purpose linear 0-1 integer programming solver. Linear programming techniques guarantees that the solution provided is optimal, and it is highly effcient to solve this kind of problems.The data mapping capabilities provided by the tool includes alignment of the arrays, one or two-dimensional distribution with BLOCK or CYCLIC fashion, a set of remapping actions to be performed between phases if profitable, plus the parallelization strategy associated. The effects of control flow statements between phases are taken into account in order to improve the accuracy of the model. The novelty of the approach resides in handling all stages of the data distribution problem, that traditionally have been treated in several independent phases, in a single step, and providing an optimal solution according to our model.

No description available.