A melhora da confiabilidade em redes de distribuição de energia elétrica é um tema importante para as indústrias de fornecimento de eletricidade, devido aos regulamentos estritos em muitos países. Depois de uma falha na rede, algumas chaves são usadas para isolar a falha, enquanto outras restauram a energia a alguns consumidores. A ótima seleção das chaves que serão abertas ou fechadas para restaurar a energia é conhecido como o problema de restauração de serviço. A instalação de chaves em posições estratégicas pode reduzir o tempo de parada, e assim melhorar a confiabilidade da rede. A seleção ótima de posições para instalar chaves é conhecido como o problema de alocação de chaves. Estes dois problemas estão relacionados estreitamente. Esta dissertação estuda o problema de alocação de chaves, considerando o problema de restauração de serviço como um subproblema. Dois métodos são propostos para estimar a confiabilidade de uma rede de distribuição com um conjunto dado de chaves instaladas. O foco principal está nas heurísticas para resolver o problema composto. Propõe-se aqui métodos como busca tabu, procedimento de busca gulosa adaptativa aleatória (sigla em inglês: GRASP), e procedimento iterativo de construção por amostras com reconexão de caminhos. Também estuda-se o benefício dos métodos de construção gulosa, semigulosa, aleatória e por amostras, e estuda-se o desempenho das estratégias de busca local por amostras, primeira melhoria e melhor melhoria. Os diferentes métodos são comparados e analisados. Os resultados mostram que os métodos por amostras são baratos e levam a soluções de boa qualidade. O procedimento iterativo de construção por amostras com reconexão de caminhos é o melhor método proposto para resolver o problema composto que é proposto nesta dissertação. / The improvement of reliability in electrical power distribution networks is an important issue for electricity supply industries, due to strict regulations in many countries. After a failure in the network, some switches are used to isolate the failure, while others restore the energy to some consumers. The optimal selection of the switches to open or close to restore energy is called the service restoration problem. The installation of switches in strategic places may reduce the outage time in case of blackouts, and thus improve the reliability of the network. The optimal selection of places to install switches is called the switch allocation problem. These two problems are closely related. This dissertation studies the switch allocation problem, considering the service restoration problem as a sub-problem. Two methods are proposed to estimate the reliability of a distribution network with a given set of installed switches. The main focus is in heuristics to solve the joint problem. It proposes methods like tabu search, greedy randomized adaptive search procedure, and iterated sample construction with path relinking. It also studies the benefit of greedy, semigreedy, random, and sample construction methods, and studies the performance of sample, first improvement and best improvement local search strategies. The different methods are compared and analyzed. The results show that sample approaches are inexpensive and lead to solutions of good quality. Iterated sample construction with path relinking is the best method to solve the joint problem that is proposed in this dissertation.

A melhora da confiabilidade em redes de distribuição de energia elétrica é um tema importante para as indústrias de fornecimento de eletricidade, devido aos regulamentos estritos em muitos países. Depois de uma falha na rede, algumas chaves são usadas para isolar a falha, enquanto outras restauram a energia a alguns consumidores. A ótima seleção das chaves que serão abertas ou fechadas para restaurar a energia é conhecido como o problema de restauração de serviço. A instalação de chaves em posições estratégicas pode reduzir o tempo de parada, e assim melhorar a confiabilidade da rede. A seleção ótima de posições para instalar chaves é conhecido como o problema de alocação de chaves. Estes dois problemas estão relacionados estreitamente. Esta dissertação estuda o problema de alocação de chaves, considerando o problema de restauração de serviço como um subproblema. Dois métodos são propostos para estimar a confiabilidade de uma rede de distribuição com um conjunto dado de chaves instaladas. O foco principal está nas heurísticas para resolver o problema composto. Propõe-se aqui métodos como busca tabu, procedimento de busca gulosa adaptativa aleatória (sigla em inglês: GRASP), e procedimento iterativo de construção por amostras com reconexão de caminhos. Também estuda-se o benefício dos métodos de construção gulosa, semigulosa, aleatória e por amostras, e estuda-se o desempenho das estratégias de busca local por amostras, primeira melhoria e melhor melhoria. Os diferentes métodos são comparados e analisados. Os resultados mostram que os métodos por amostras são baratos e levam a soluções de boa qualidade. O procedimento iterativo de construção por amostras com reconexão de caminhos é o melhor método proposto para resolver o problema composto que é proposto nesta dissertação. / The improvement of reliability in electrical power distribution networks is an important issue for electricity supply industries, due to strict regulations in many countries. After a failure in the network, some switches are used to isolate the failure, while others restore the energy to some consumers. The optimal selection of the switches to open or close to restore energy is called the service restoration problem. The installation of switches in strategic places may reduce the outage time in case of blackouts, and thus improve the reliability of the network. The optimal selection of places to install switches is called the switch allocation problem. These two problems are closely related. This dissertation studies the switch allocation problem, considering the service restoration problem as a sub-problem. Two methods are proposed to estimate the reliability of a distribution network with a given set of installed switches. The main focus is in heuristics to solve the joint problem. It proposes methods like tabu search, greedy randomized adaptive search procedure, and iterated sample construction with path relinking. It also studies the benefit of greedy, semigreedy, random, and sample construction methods, and studies the performance of sample, first improvement and best improvement local search strategies. The different methods are compared and analyzed. The results show that sample approaches are inexpensive and lead to solutions of good quality. Iterated sample construction with path relinking is the best method to solve the joint problem that is proposed in this dissertation.

A melhora da confiabilidade em redes de distribuição de energia elétrica é um tema importante para as indústrias de fornecimento de eletricidade, devido aos regulamentos estritos em muitos países. Depois de uma falha na rede, algumas chaves são usadas para isolar a falha, enquanto outras restauram a energia a alguns consumidores. A ótima seleção das chaves que serão abertas ou fechadas para restaurar a energia é conhecido como o problema de restauração de serviço. A instalação de chaves em posições estratégicas pode reduzir o tempo de parada, e assim melhorar a confiabilidade da rede. A seleção ótima de posições para instalar chaves é conhecido como o problema de alocação de chaves. Estes dois problemas estão relacionados estreitamente. Esta dissertação estuda o problema de alocação de chaves, considerando o problema de restauração de serviço como um subproblema. Dois métodos são propostos para estimar a confiabilidade de uma rede de distribuição com um conjunto dado de chaves instaladas. O foco principal está nas heurísticas para resolver o problema composto. Propõe-se aqui métodos como busca tabu, procedimento de busca gulosa adaptativa aleatória (sigla em inglês: GRASP), e procedimento iterativo de construção por amostras com reconexão de caminhos. Também estuda-se o benefício dos métodos de construção gulosa, semigulosa, aleatória e por amostras, e estuda-se o desempenho das estratégias de busca local por amostras, primeira melhoria e melhor melhoria. Os diferentes métodos são comparados e analisados. Os resultados mostram que os métodos por amostras são baratos e levam a soluções de boa qualidade. O procedimento iterativo de construção por amostras com reconexão de caminhos é o melhor método proposto para resolver o problema composto que é proposto nesta dissertação. / The improvement of reliability in electrical power distribution networks is an important issue for electricity supply industries, due to strict regulations in many countries. After a failure in the network, some switches are used to isolate the failure, while others restore the energy to some consumers. The optimal selection of the switches to open or close to restore energy is called the service restoration problem. The installation of switches in strategic places may reduce the outage time in case of blackouts, and thus improve the reliability of the network. The optimal selection of places to install switches is called the switch allocation problem. These two problems are closely related. This dissertation studies the switch allocation problem, considering the service restoration problem as a sub-problem. Two methods are proposed to estimate the reliability of a distribution network with a given set of installed switches. The main focus is in heuristics to solve the joint problem. It proposes methods like tabu search, greedy randomized adaptive search procedure, and iterated sample construction with path relinking. It also studies the benefit of greedy, semigreedy, random, and sample construction methods, and studies the performance of sample, first improvement and best improvement local search strategies. The different methods are compared and analyzed. The results show that sample approaches are inexpensive and lead to solutions of good quality. Iterated sample construction with path relinking is the best method to solve the joint problem that is proposed in this dissertation.

Tesis por compendio / La red en el chip (NoC) se han convertido en el elemento clave para la comunicación eficiente entre los núcleos dentro de los chip multiprocesador (CMP). Tanto el uso de aplicaciones paralelas en los CMPs como el incremento de la cantidad de memoria necesitada por las aplicaciones, ha impulsado que la red de comunicación gane una mayor importancia. La NoC es la encargada de transportar toda la información requerida por los núcleos. Además, el incremento en el número de núcleos en los CMPs impulsa las NoC a ser diseñadas de forma escalable, pero al mismo tiempo sin que esto afecte a las prestaciones de la red (latencia y productividad). Por tanto, el diseño de la red en el chip se convierte en crítico. Esta tesis presenta diferentes propuestas que atacan el problema de la mejora de las prestaciones de la red en tres escenarios distintos. Los tres escenarios en los que se centran nuestras propuestas son: 1) NoCs que implementan un algoritmo de encaminamiento adaptativo, 2) escenarios con necesidad de tiempos de acceso a memoria bajos y 3) sistemas con previsión de seguridad a nivel de aplicación. Las primeras propuestas se centran en el aumento de la productividad en la red utilizando algoritmos de encaminamiento adaptativos mediante un mejor uso de los recursos de la red, primera propuesta SUR, y evitando que se ramifique la congestión cuando existe tráfico intenso hacia un único destinatario, segunda propuesta EPC. La tercera y principal contribución de esta tesis se centra la problemática de reducir el tiempo de acceso a memoria. PROSA, mediante un diseño híbrido de conmutación de paquete y conmuntación de circuito, permite reducir la latencia de la red aprovechando la latencia de acceso a memoria para establecer circuitos. De esta forma cuando la información llega a la NoC, esta es servida sin retardos. Por último, la propuesta Token Based TDM se centra en el escenario con redes de interconexión seguras. En este tipo de NoC las aplicaciones esta divididas en dominios y la red debe garantizar que no existen interferencias entre los diferentes dominios para evitar de este modo la intrusión de posibles aplicaciones maliciosas. Token-based TDM permite el aislamiento de los dominios sin tener impacto en el diseño de los conmutados de la NoC. Los resultados obtenidos demuestran como estas propuestas han servido para mejorar las prestaciones de la red en los diferentes escenarios. La implementación y la simulación de las propuestas muestra como mediante el balanceado de la utilización de los recursos de la red, los CMPs con algoritmos de encaminamiento adaptativos son capaces de aumentar el tráfico soportado por la red. Además, el uso de un filtro para limitar el encaminamiento adaptativo en situaciones de congestión previene a los mensajes de la ramificación de la congestión a lo largo de la red. Por otra parte, los resultados demuestran que el uso combinado de la conmutación de paquete y conmutación de circuito reduce muy significativa de la latencia de red acceso a memoria, contribuyendo a una reducción significativa del tiempo de ejecución de la aplicación. Por último, Token-Based TDM incrementa las prestaciones de las redes TDM debido a su alta flexibilidad dado que no requiere ninguna modificación en la red para soportar una cantidad diferente de dominios mientras mejora la latencia de la red y mantiene un aislamiento perfecto entre los tráficos de las aplicaciones. / The Network on Chip (NoC) has become the key element for an efficient communication between cores within the multiprocessor chip (CMP). The use of parallel applications in CMPs and the increase in the amount of memory needed by applications have pushed the network communication to gain importance. The NoC is in charge of transporting all the data needed by the processors cores. Moreover, the increase in the number of cores pushes the NoCs to be designed in a scalable way, but at the same time, without affecting network performance (latency and productivity). Thus, network-on-chip design becomes critical. This thesis presents different proposals that attack the problem of improving the network performance in three different scenarios. The three scenarios in which our proposals are focused are: 1) NoCs with an adaptive routing algorithm, 2) scenarios with low memory access time needs, and 3) high-assurance NoCs. The first proposals focus on increasing network throughput with adaptive routing algorithms via the improvement of the network resources utilization, the first proposal SUR, and avoiding congestion spreading when an intense traffic to a single destination occurs, second proposal ECP. The third one and main contribution of this thesis focuses on the problem of reducing memory access latency. PROSA, through a hybrid circuit-packet switching architecture design, reduces the network latency by getting benefit of the memory access latency slack and to establishing circuits during that delay. In this way the information when arrives to the NoC is served without any delay. Finally, the proposal Token-Based TDM focuses on the scenario with high assurance networks on chips. In this type of NoCs the applications are divided into domains and the network must guarantee that there are no interferences between the different domains avoiding this way intrusion of possible malicious applications. Token-based TDM allows domain isolation with no design impact on NoC routers. The results show how these proposals improve the performance of the network in each different scenario. The implementation and simulations of the proposals show the efficient use of network resources in CMPs with adaptive routing algorithms which leads to an increasement of the injected traffic supported by the network. In addition, using a filter to limit the adaptivity of the routing algorithm under congested situations prevents messages from spreading the congestion along the network. On the other hand, the results show that the combined use of circuit and packet switching reduces the memory access latency significantly, contributing to a significant reduction in application execution time. Finally, Token-Based TDM increases network performance of TDM networks due to its high flexibility and efficient arbitration. Moreover, Token-Based TDM does not require any modification in the network to support a different number of domains while improving latency and keeping a strong traffic isolation from different domains. / La xarxa en el xip (NoC) s'ha convertit en un element clau per a una comunicació eficient entre els diferents nuclis dins d'un xip multiprocessador (CMP). Tant la utilització d'aplicacions paral·leles en el CMP com l'increment de la quantitat de memòria necessitada per les aplicacions, hi ha produït que la xarxa de comunicació tinga una major importància. La NoC és l'encarregada de transportar tota la informació necessària pels nuclis. A més, l'increment del nombre de nuclis dins del CMP fa que la NoC haja de ser dissenyada d'una forma escalable, sense que afecte les prestacions de la xarxa (latència i productivitat). Per tant, el disseny de la xarxa en el xip es converteix crític. Aquesta tesi presenta diferents propostes que ataquen el problema de la millora de les prestacions de la xarxa en tres escenaris distints. Els tres escenaris en els quals se centren les nostres propostes són: 1) NoCs que implementen un algoritme d'encaminament adaptatiu, 2) escenaris amb necessitat de temps baix d'accés a memòria i 3) sistemes amb previsió de seguretat en l'àmbit d'aplicació. Les primeres propostes se centren en l'augment de la productivitat en la xarxa utilitzant algoritmes d'encaminament adaptatiu mitjançant una millor utilització dels recursos de la xarxa, primera proposta SUR, i evitant que es ramifique la congestió quan existeix un trànsit intens cap a un únic destinatari, segona proposta EPC. La tercera i principal contribució d'aquesta tesi es basa en la problemàtica de reduir el temps d'accés a memòria. PROSA, mitjançant un disseny híbrid de commutació de paquet i commutació de circuit, redueix la latència de la xarxa aprofitant la latència d'accés a memòria i establint els circuits durant aquesta latència. D'aquesta forma la informació quan arriba a la NoC pot ser enviada sense cap retràs. Per últim, la proposta Token-based TDM se centra en l'escenari amb xarxes d'interconnexió d'alta seguretat. En aquest tipus de NoC les aplicacions estan dividides en dominis i la xarxa deu garantir que no existeixen interferències entre els diferents dominis per a evitar d'aquesta forma la intrusió de possibles aplicacions malicioses. Token-based TDM permet l'aïllament dels dominis sense tindre impacte en el disseny dels encaminadors de la NoC. Els resultats demostren com aquestes propostes han servit per a millorar les prestacions de la xarxa en els diferents escenaris. La seua implementació i simulació demostra com mitjançant el balancejat de la utilització dels recursos de la xarxa, els CMP amb algoritmes d'encaminament adaptatiu són capaços d'augmentar el trànsit suportat per la xarxa. A més, l'ús d'un filtre per a limitar l'adaptabilitat de l'encaminament adaptatiu en situacions de congestió permet prevenir els missatges de la congestió al llarg de la xarxa. Per altra banda, els resultats demostren que l'ús combinat de la commutació de paquet i commutació de circuit redueix molt significativament de la latència d'accés a memòria, contribuint en una reducció significativa del temps d'execució de l'aplicació. Per últim, Token-based TDM incrementa les prestacions de les xarxes TDM debut a la seua alta flexibilitat donat que no requereix cap modificació en la xarxa per a suportar una quantitat diferent de dominis mentre millora la latència de la xarxa i mantén un aïllament perfecte entre els trànsits de les aplicacions. / Gorgues Alonso, M. (2018). Improving Network-on-Chip Performance in Multi-Core Systems [Tesis doctoral]. Universitat Politècnica de València. https://doi.org/10.4995/Thesis/10251/107336 / Compendio