Microgrid deployment in electric grids improves reliability, efficiency, and quality, as well as the overall sustainability and resiliency of the grid. Specifically, microgrids alleviate the effects of power outages. However, microgrid implementations impose additional challenges on power systems. Microgrid protection is one of the technical challenges implicit in the deployment of microgrids. These challenges occur as a result of the unique properties of microgrid networks in comparison to traditional electrical networks. Differential protection is a fast, selective, and sensitive technique. Additionally, it offers a viable solution to microgrid protection concerns. The differential zone protection scheme is a cost-effective variant of differential protection. To implement a differential zone protection scheme, the network must be split into different protection zones. The reliability of this protection scheme is dependent upon the number of protective zones developed. This thesis proposes a new differential zone protection scheme using a graph partitioning algorithm. A graph partitioning algorithm is used to partition the microgrid into multiple protective zones. The IEEE 13-node microgrid is used to demonstrate the proposed protection scheme. The protection scheme is validated with MATLAB Simulink, and its impact is simulated with DIgSILENT PowerFactory software. Additionally, a comprehensive comparison was made to a comparable differential zone protection scheme. / Master of Science / A microgrid is a group of connected distributed energy resources (DERs) with the loads to be served that acts as a local electrical network. In electric grids, microgrid implementation enhances grid reliability, efficiency, and quality, as well as the system's overall sustainability and resiliency. Microgrids mitigate the consequences of power disruptions. Microgrid solutions, on the other hand, bring extra obstacles to power systems. One of the technological issues inherent in the implementation of microgrids is microgrid protection. These difficulties arise as a result of microgrid networks' distinct characteristics as compared to standard electrical networks. Differential protection is a technique that is fast, selective, and sensitive. It also provides a feasible solution to microgrid protection problems. This protection scheme, on the other hand, is more expensive than others. The differential zone protection scheme is a cost-effective variation of differential protection that lowers protection scheme expenses while improving system reliability. The network must be divided into different protection zones in order to deploy a differential zone protection scheme. The number of protective zones generated determines the reliability of this protection method. Using a network partitioning technique, this thesis presents a new differential zone protection scheme. The microgrid is divided into various protection zones using a graph partitioning algorithm. The proposed protection scheme is demonstrated using the IEEE 13-node microgrid. MATLAB Simulink is used to validate the protection scheme, while DIgSILENT PowerFactory is used to simulate its impact. A comparison of a similar differential zone protection scheme was also done.

Over the past two decades, microprocessor manufacturers have typically relied on wider issue widths and deeper pipelines to obtain performance improvements for single threaded applications. However, in the recent years, with power dissipation and wire delays becoming primary design constraints, this approach can no longer be effectively used to yield performance improvements. Thus process designers and vendors are universally moving towards multi-core designs. Examples for these are the commodity general purpose multi-core processors, the CellBE accelerator from IBM and the Graphics Processing Units from NVIDIA and ATI. Although these many and multi-core architectures can provide enormous performance benefits, it is difficult to program for them due to the complexity of writing explicitly parallel code. The ubiquity of computationally intensive media processing applications makes it imperative to consider new programming frameworks and languages that can express parallelism in an easy, portable manner. The StreamIt programming language has been proposed to efficiently exploit parallelism at various levels on general purpose multi-core architectures and stream processors and allow media processing and DSP application to be developed in an easy and portable fashion. The StreamIt model allows programmers to specify a program as a set of filters connected by FIFO communication channels. The graphs thus specified by the StreamIt programs describe task, data and pipeline parallelism which can be potentially exploited on modern Graphics Processing Units (GPUs), which have emerged as powerful, commodity stream processors, which support abundant parallelism in hardware. The first part of this thesis deals with the challenges in mapping StreamIt programs to GPUs and proposes an efficient technique to software pipeline the execution of stream Programs on GPUs. We formulate this problem—both scheduling and assignment of filters to processors—as an efficient Integer Linear Program(ILP), which is then solved using ILP solvers. We also describe a novel buffer layout technique for GPUs which facilitates exploiting the high memory bandwidth available in GPUs. The proposed scheduling utilizes both the scalar units in GPU, to exploit data parallelism, and multiprocessors, to exploit task and pipeline parallelism. We have evaluated our approach on a platform equipped with an NVIDIA GeForce 8800 GTS 512 GPU and our approach yields a (geometric) mean speedup of 5.02X, with a maximum speedup of 36.83X across a set of StreamIt benchmarks, with the speedup measured relative to an optimized single threaded CPU execution. While the approach of software pipelining the execution of stream programs on GPUs is efficient and performs well, it does not utilize the CPU cores to perform useful computation. Further, it does not support programs with stateful filters, which are essentially filters that are not data parallel owing to a dependence between each successive firing that is carried through the implicit state of the filter. The second part of the thesis aims at addressing these issues and describes a novel method to orchestrate the execution of a StreamIt program on the multiple cores of a system and GPUs in a synergistic manner. The proposed approach identifies, using profiling, the relative benefits of executing a task on the superscalar CPU cores and the accelerator. We formulate the problem of partitioning the work between the CPU cores and the GPU, taking into account the latencies for data transfers, the limited DMA bandwidth available and the required buffer layout transformations associated with the partitioning, as an integrated Integer Linear Program(ILP) which can then be solved by an ILP solver. Since solving an ILP is NP-Hard in the general case and may thus require a large amount of time, we also propose an efficient heuristic algorithm for the work partitioning between the CPU and the GPU, which provides solutions which are within 9.05% of the optimal solutions to the ILP formulation on an average across the benchmark suite, while requiring 2–3 orders of magnitude less time than the ILP approach. The partitioned tasks are then software pipelined to execute on the multiple CPU cores and the Streaming Multiprocessors (SMs) of the GPU. The software pipelining algorithm orchestrates the execution between CPU cores and the GPU by emitting the code for the CPU and the GPU, and the code for the required data transfers. Our experiments on a platform with eight CPU cores, out of which four were used, and a GeForce 8800 GTS512 GPU show a(geometric) mean speed up of 6.84X with a maximum of 51.96X over a single threaded CPU execution across a set of StreamIt benchmarks.

Submitted by Johnny Rodrigues (johnnyrodrigues@ufcg.edu.br) on 2018-07-27T17:11:09Z No. of bitstreams: 1 DANIEL CARDOSO DE SOUZA - TESE PPGEE 2006..pdf: 1923363 bytes, checksum: e0aa0e758bff14f247b303ddfe8d8f33 (MD5) / Made available in DSpace on 2018-07-27T17:11:09Z (GMT). No. of bitstreams: 1 DANIEL CARDOSO DE SOUZA - TESE PPGEE 2006..pdf: 1923363 bytes, checksum: e0aa0e758bff14f247b303ddfe8d8f33 (MD5) Previous issue date: 2006-12 / Capes / Este trabalho tem como objetivo propor um algoritmo de particionamento hardware/software otimizado. Trabalha-se com a hipótese de que algumas características específicas de certos algoritmos já publicados possam ser combinadas vantajosamente, levando ao aprimoramento de um algoritmo de particionamento de base, e conseqüentemente dos sistemas heterogêneos gerados por ele. O conjunto de otimizações propostas para serem realizadas nesse novo algoritmo consiste de: generalização das arquiteturas-alvo candidatas com a inclusão de FPGA’s para o particionamento, consideração precisa dos custos e potências das funções mapeadas em hardware, agendamento de sistemas com hardware reconfigurável dinamicamente, e consideração de múltiplas alternativas de implementação de um nó de aplicação em um mesmo processador. Essas otimizações são implementadas em sucessivas versões do algoritmo de particionamento proposto, que são testadas com duas aplicações de processamento de sinais. Os resultados do particionamento demonstram o efeito de cada otimização na qualidade do sistema heterogêneo obtido. / This work’s goal is to propose an optimized hardware/software partitioning algorithm. We work on the hypothesis that some specific features of certain published algorithms can be advantageously combined for the improvement of a base partitioning algorithm, and of its generated heterogeneous systems. The set of optimizations proposed for the achievement of this new algorithm encompass: generalization of candidate target architectures with the inclusion of FPGA’s for the partitioning, precise consideration of functions’ implementation costs and power consumptions in hardware, manipulation of systems with dynamically reconfigurable hardware, and consideration of multiple implementation alternatives for an application node in a given processor. These optimizations are implemented in successive versions of the proposed partitioning algorithm, which are tested with two signal processing applications. The partitioning results demonstrate the effect of each optimization on the achieved heterogeneous system quality. / Resumé: Cette thèse a pour but de proposer un algorithme de partitionnement matériel/logiciel optimisé. On travaille sur l’hypothèse de que quelques caractéristiques spécifiques à certains algorithmes déjà publiés puissent être combinées de façon avantageuse, menant à l’amélioration d’un algorithme de partitionnement de base et, par conséquence, des systèmes hétérogènes générés par cet algorithme. L’ensemble d’optimisations proposées pour être réalisées dans ce nouvel algorithme consiste en: généralisation des architecturescible candidates avec l’ajout de FPGA’s pour le partitionnement, considération précise des coûts et puissances des fonctions allouées en matériel, ordonnancement de systèmes au matériel dynamiquement reconfigurable, et prise en compte de plusieurs alternatives d’implémentation d’un noeud d’application dans un même processeur. Ces optimisations sont implémentées en versions successives de l’algorithme de partitionnement proposé, lesquelles sont testées avec deux applications de traitement du signal. Les résultats du partitionnement démontrent l’effet de chaque optimisation sur la qualité du système hétérogène obtenu.

In this thesis we consider the problem of clustering the data lying in a union of subspaces using spectral methods. Though the data generated may have high dimensionality, in many of the applications, such as motion segmentation and illumination invariant face clustering, the data resides in a union of subspaces having small dimensions. Furthermore, for a number of classification and inference problems, it is often useful to identify these subspaces and work with data in this smaller dimensional manifold. If the observations in each cluster were to be distributed around a centric, applying spectral clustering on an a nifty matrix built using distance based similarity measures between the data points have been used successfully to solve the problem. But it has been observed that using such pair-wise distance based measure between the data points to construct a similarity matrix is not sufficient to solve the subspace clustering problem. Hence, a major challenge is to end a similarity measure that can capture the information of the subspace the data lies in. This is the motivation to develop methods that use an affinity tensor by calculating similarity between multiple data points. One can then use spectral methods on these tensors to solve the subspace clustering problem. In order to keep the algorithm computationally feasible, one can employ column sampling strategies. However, the computational costs for performing the tensor factorization increases very quickly with increase in sampling rate. Fortunately, the advances in GPU computing has made it possible to perform many linear algebra operations several order of magnitudes faster than traditional CPU and multicourse computing. In this work, we develop parallel algorithms for subspace clustering on a GPU com-putting environment. We show that this gives us a significant speedup over the implementations on the CPU, which allows us to sample a larger fraction of the tensor and thereby achieve better accuracies. We empirically analyze the performance of these algorithms on a number of synthetically generated subspaces con gyrations. We ally demonstrate the effectiveness of these algorithms on the motion segmentation, handwritten digit clustering and illumination invariant face clustering and show that the performance of these algorithms are comparable with the state of the art approaches.