Reducción del Tiempo de Simulación de Redes de Distribución de Agua, mediante el Método de Mallas y la Computación de Altas Prestaciones

Abstract

[EN] Computer simulation of water distribution networks by means of mathematical models is nowadays an indispensable tool for the design and exploitation of those networks. Simulation is used not only for the design of new supply systems, or modifications and extensions of existing systems, but also for the normal operation tasks carried out in any network. Two main types of simulation can be differentiated: hydraulic simulation, by means of which the pressures and flows registered in the network are computed, and water quality simulation, the objective of which is to obtain information about chemical substance concentrations.

The need for simulation comes often in the context of a wider problem of optimization or reliability analysis, which requires performing a large number of simulations, thus resulting in a process with considerable computational complexity. This fact, added to the growing size and level of detail of network models, as a consequence of the automatic incorporation of data coming from Geographical Information Systems, means that the performance of the simulation solver has a great impact in the overall computing time.

In this context, this thesis considers and explores different strategies to improve the performance of water distribution network simulation. The first strategy consists of making some contributions to the hydraulic simulation method known as Looped Newton-Raphson (or more simply the loop method), which is based on the consideration of flow corrections associated to a set of independent loops within the network. Even though the method known as Global Gradient Algorithm (GGA) is more widely used and accepted, the loop method has the potential to be faster, owing to the smaller size of the underlying linear systems. In this thesis some contributions are presented to improve the performance of the loop method for hydraulic simulation. Firstly, efficient algorithms are developed for the selection of a suitable set of independent loops, leading to a highly sparse linear system. Secondly, methods are developed for efficient modeling of hydraulic valves, and especially pressure reducing/sustaining valves.

The second strategy explored is the introduction of high performance computing in the hydraulic simulation using distributed memory platforms. In particular, the code of Epanet, a widely accepted water distribution network simulation software, is taken as the starting point for the introduction of parallel simulation algorithms, using the Message Passing Interface (MPI) tool for inter-process communications. As a result of this work, firstly a parallel algorithm is presented for the simulation of flows and pressures by means of the GGA method, making use of multifrontal algorithms for the parallel solution of the underlying linear systems. Secondly, a parallel algorithm for water quality simulation by means of the Discrete Volume Element Method (DVEM) is described, based on partitioning the network by means of multilevel recursive bisection algorithms. Thirdly, a parallel method is presented for leakage minimization by finding the optimal pressure settings for a set of pressure-reducing valves.

In distributed memory platforms the overhead due to communication and synchronization can be excessively high, counterbalancing the gain derived from the division of the computation among the processors. This effect is less pronounced in shared memory platforms such as multicore systems, which have gained popularity over the last years. This fact motivates the third strategy explored in this thesis, which is the development of parallel algorithms for simulation of flows and pressures using multicore systems. OpenMP is the tool used for the parallelization, both of the method GGA as implemented in Epanet software and of the loop method with the contributions on it that have been made in the context of this thesis.

[ES] La simulación por computador de las redes de distribución de agua potable, mediante el uso de modelos matemáticos, es hoy en día una herramienta indispensable para el diseño y la explotación de dichas redes. La simulación se utiliza tanto en el diseño de nuevos abastecimientos y en ampliaciones o modificaciones de abastecimientos existentes, como en las tareas de operación normales de cualquier red. Se puede diferenciar entre dos tipos de simulación: la simulación hidráulica, que permite obtener las presiones y caudales que se registran en la red, y la simulación de la calidad del agua, cuyo objetivo es obtener información sobre concentraciones de sustancias químicas.

A menudo la necesidad de simulación surge dentro de un problema más amplio de optimización o de análisis de fiabilidad, que requiere llevar a cabo un gran número de simulaciones, con lo que el proceso completo resulta de una complejidad computacional considerable. Esto, añadido al hecho de que el tamaño y nivel de detalle de los modelos de redes crece constantemente, como consecuencia de la incorporación automática de datos contenidos en Sistemas de Información Geográfica, hace que las prestaciones del solver de simulación tengan un gran impacto en el tiempo total de cálculo necesario.

En este contexto, esta tesis considera y explora distintas vías para mejorar las prestaciones de la simulación de redes de distribución de agua. La primera de estas vías consiste en realizar algunas aportaciones al método de simulación hidráulica conocido como método de Newton-Raphson de mallas, el cual se basa en la consideración de caudales correctores asociados a un conjunto de mallas independientes definidas sobre la red. Aunque el método conocido como Algoritmo del Gradiente Global (GGA) goza de mayor aceptación, el método de mallas tiene el potencial de ser más rápido, debido al menor tamaño de los sistemas lineales subyacentes. Esta tesis presenta aportaciones para mejorar las prestaciones del método de mallas de simulación hidráulica. En primer lugar, se desarrollan algoritmos eficientes para la selección de un conjunto de mallas adecuado, que conduzca a un sistema altamente disperso. En segundo lugar se desarrollan métodos para la modelización eficiente de válvulas, y especialmente válvulas reductoras/sostenedoras de presión.

La segunda vía explorada es la introducción de la computación de altas prestaciones en la simulación hidráulica usando plataformas de memoria distribuida. En particular, se parte del código de Epanet, un software de simulación de redes de amplia aceptación, y se introducen en él algoritmos paralelos de simulación, usando la herramienta Message Passing Interface (MPI) para la comunicación entre procesos. Como resultado de ello, se presenta en primer lugar un algoritmo paralelo para la simulación de caudales y presiones por medio del método GGA, haciendo uso de algoritmos multifrontales para la resolución paralela de los sistemas lineales subyacentes. En segundo lugar, se describe un algoritmo paralelo para la simulación de la calidad del agua mediante el Método de Elementos Discretos de Volumen (DVEM), particionando la red por medio de algoritmos de bisección recursiva multinivel. En tercer lugar, se presenta un método paralelo para la minimización de fugas mediante la determinación de las consignas óptimas de una serie de válvulas reductoras de presión.

Finalmente, la tercera vía explorada es el desarrollo de algoritmos paralelos sobre memoria compartida para la simulación de presiones y caudales. Se considera con ello un tipo de plataformas que han ganado popularidad en los últimos años. Se utiliza la herramienta OpenMP para la paralelización, tanto de Epanet y de su implementación del método GGA, como del método de mallas, con las aportaciones al mismo que se han realizado en el contexto de esta tesis.

[CA] La simulació per computador de les xarxes de distribució d'aigua potable, per mitjà de l'ús de models matemàtics, es hui en dia una ferramenta indispensable per al disseny i l'explotació d'abastiments d'aigua. La simulació s'utilitza tant per al disseny de nous abastiments o ampliacions i modificacions d'abastiments existents, com per a les tasques d'operació normals en qualsevol xarxa. Es pot diferenciar entre dos tipus de simulació: la simulació hidràulica, que permet obtindre les pressions i cabals que es produeixen en la xarxa, i la simulació de la qualitat de l'aigua, l'objectiu de la qual és obtindre informació sobre concentracions de substàncies químiques.

Sovint la necessitat de simulació sorgeix dins d'un problema més ampli d'optimització o d'anàlisi de fiabilitat, que requereix dur a terme un gran nombre de simulacions, amb la qual cosa el procés complet resulta d'una complexitat computacional considerable. Això, afegit al fet de que la grandària i nivell de detall del models de xarxes creix constantment, com a conseqüència de la incorporació automàtica de dades contingudes en Sistemes d'Informació Geogràfica, fa que les prestacions del solver de simulació tinguen un gran impacte en el temps total de càlcul necessari.

En este context, esta tesi considera i explora diferents vies per a millorar les prestacions de la simulació de xarxes de distribució d'aigua. La primera d'estes vies consisteix en realitzar algunes contribucions al mètode de simulació hidràulica conegut com mètode de Newton-Raphson de malles (o simplement mètode de malles), el qual es basa en la consideració de cabals correctors associats a un conjunt de malles independents definides en la xarxa. Encara que el mètode conegut com Algorisme del Gradient Global (GGA) gaudeix de major acceptació, el mètode de malles té el potencial de ser més ràpid, degut a la menor grandària dels sistemes lineals subjacents. En esta tesi es presenten contribucions per a millorar les prestacions del mètode de malles de simulació hidràulica. En concret, en primer lloc es desenvolupen algorismes eficients per a la selecció d'un conjunt de malles adequat, que conduïsca a un sistema lineal altament dispers. En segon lloc es desenvolupen mètodes per a la modelització eficient de vàlvules, i especialment vàlvules reductores/sostenidores de pressió.

La segona via explorada és la introducció de la computació d'altes prestacions en la simulació hidràulica utilitzant plataformes de memòria distribuïda. En concret, es parteix del codi d'Epanet, un programari de simulació de xarxes de distribució d'aigua d'amplia acceptació, i s'hi introdueixen algorismes paral·lels de simulació, utilitzant la ferramenta Message Passing Interface (MPI) per a la comunicació entre processos. Com a resultat d'este treball, es presenta en primer lloc un algorisme paral·lel per a la simulació de cabals i pressions per mitjà del mètode GGA, fent ús d'algorismes multifrontals per a la resolució en paral·lel dels sistemes lineals subjacents. En segon lloc, es descriu un algorisme paral·lel per a la simulació de la qualitat d'aigua amb el Mètode d'Elements Discrets de Volum (DVEM), particionant la xarxa per mitjà d'algoritmes de bisecció recursiva multinivell. En tercer lloc es presenta un mètode paral·lel per a la minimització de fugues mitjançant la determinació de les consignes òptimes d'una sèrie de vàlvules reductores de pressió.

Finalment, la tercera via explorada és el desenvolupament d'algorismes paral·lels sobre memòria compartida per a la simulació de pressions i cabals. Es considera amb això un tipus de plataformes que han guanyat popularitat en els últims anys. S'utilitza la ferramenta OpenMP per a la paral·lelització, tant del programari Epanet i de la seua implementació del mètode GGA, com del mètode de malles, amb les contribucions al mateix que s'han realitzat en el context d'esta tesi.