O paradigma Network Function Virtualization (NFV) promete tornar as redes de computadores mais escaláveis e flexíveis, através do desacoplamento das funções de rede de hardware dedicado e fornecedor específico. No entanto, funções de rede computacionalmente intensivas podem ser difíceis de virtualizar sem degradação de desempenho. Neste contexto, Field-Programmable Gate Arrays (FPGAs) têm se mostrado uma boa opção para aceleração por hardware de funções de rede virtuais que requerem alta vazão, sem se desviar do conceito de uma infraestrutura NFV que visa alta flexibilidade. A avaliação de expressões regulares é um mecanismo importante e computacionalmente intensivo, usado para realizar Deep Packet Inpection, que pode ser acelerado por FPGA para atender aos requisitos de desempenho. Esta solução, no entanto, apresenta novos desafios em relação aos requisitos de confiabilidade. Particularmente para FPGAs baseados em SRAM, soft errors na memória de configuração são uma ameaça de confiabilidade significativa. Neste trabalho, apresentamos um mecanismo de tolerância a falhas abrangente para lidar com falhas de configuração na funcionalidade de módulos de avaliação de expressões regulares baseados em FPGA. Além disso, é introduzido um mecanismo de correção de erros que considera o posicionamento desses módulos no FPGA para reduzir o tempo de reparo do sistema, melhorando a confiabilidade e a disponibilidade. Os resultados experimentais mostram que a taxa de falha geral e o tempo de reparo do sistema podem ser reduzidos em 95% e 90%, respectivamente, com custos de área e performance admissíveis. / The Network Function Virtualization (NFV) paradigm promises to make computer networks more scalable and flexible by decoupling the network functions (NFs) from dedicated and vendor-specific hardware. However, network and compute intensive NFs may be difficult to virtualize without performance degradation. In this context, Field-Programmable Gate Arrays (FPGAs) have been shown to be a good option for hardware acceleration of virtual NFs that require high throughput, without deviating from the concept of an NFV infrastructure which aims at high flexibility. Regular expression matching is an important and compute intensive mechanism used to perform Deep Packet Inspection, which can be FPGA-accelerated to meet performance constraints. This solution, however, introduces new challenges regarding dependability requirements. Particularly for SRAM-based FPGAs, soft errors on the configuration memory are a significant dependability threat. In this work we present a comprehensive fault tolerance mechanism to deal with configuration faults on the functionality of FPGA-based regular expression matching engines. Moreover, a placement-aware scrubbing mechanism is introduced to reduce the system repair time, improving the system reliability and availability. Experimental results show that the overall failure rate and the system mean time to repair can be reduced in 95% and 90%, respectively, with manageable area and performance costs.

O paradigma Network Function Virtualization (NFV) promete tornar as redes de computadores mais escaláveis e flexíveis, através do desacoplamento das funções de rede de hardware dedicado e fornecedor específico. No entanto, funções de rede computacionalmente intensivas podem ser difíceis de virtualizar sem degradação de desempenho. Neste contexto, Field-Programmable Gate Arrays (FPGAs) têm se mostrado uma boa opção para aceleração por hardware de funções de rede virtuais que requerem alta vazão, sem se desviar do conceito de uma infraestrutura NFV que visa alta flexibilidade. A avaliação de expressões regulares é um mecanismo importante e computacionalmente intensivo, usado para realizar Deep Packet Inpection, que pode ser acelerado por FPGA para atender aos requisitos de desempenho. Esta solução, no entanto, apresenta novos desafios em relação aos requisitos de confiabilidade. Particularmente para FPGAs baseados em SRAM, soft errors na memória de configuração são uma ameaça de confiabilidade significativa. Neste trabalho, apresentamos um mecanismo de tolerância a falhas abrangente para lidar com falhas de configuração na funcionalidade de módulos de avaliação de expressões regulares baseados em FPGA. Além disso, é introduzido um mecanismo de correção de erros que considera o posicionamento desses módulos no FPGA para reduzir o tempo de reparo do sistema, melhorando a confiabilidade e a disponibilidade. Os resultados experimentais mostram que a taxa de falha geral e o tempo de reparo do sistema podem ser reduzidos em 95% e 90%, respectivamente, com custos de área e performance admissíveis. / The Network Function Virtualization (NFV) paradigm promises to make computer networks more scalable and flexible by decoupling the network functions (NFs) from dedicated and vendor-specific hardware. However, network and compute intensive NFs may be difficult to virtualize without performance degradation. In this context, Field-Programmable Gate Arrays (FPGAs) have been shown to be a good option for hardware acceleration of virtual NFs that require high throughput, without deviating from the concept of an NFV infrastructure which aims at high flexibility. Regular expression matching is an important and compute intensive mechanism used to perform Deep Packet Inspection, which can be FPGA-accelerated to meet performance constraints. This solution, however, introduces new challenges regarding dependability requirements. Particularly for SRAM-based FPGAs, soft errors on the configuration memory are a significant dependability threat. In this work we present a comprehensive fault tolerance mechanism to deal with configuration faults on the functionality of FPGA-based regular expression matching engines. Moreover, a placement-aware scrubbing mechanism is introduced to reduce the system repair time, improving the system reliability and availability. Experimental results show that the overall failure rate and the system mean time to repair can be reduced in 95% and 90%, respectively, with manageable area and performance costs.

O paradigma Network Function Virtualization (NFV) promete tornar as redes de computadores mais escaláveis e flexíveis, através do desacoplamento das funções de rede de hardware dedicado e fornecedor específico. No entanto, funções de rede computacionalmente intensivas podem ser difíceis de virtualizar sem degradação de desempenho. Neste contexto, Field-Programmable Gate Arrays (FPGAs) têm se mostrado uma boa opção para aceleração por hardware de funções de rede virtuais que requerem alta vazão, sem se desviar do conceito de uma infraestrutura NFV que visa alta flexibilidade. A avaliação de expressões regulares é um mecanismo importante e computacionalmente intensivo, usado para realizar Deep Packet Inpection, que pode ser acelerado por FPGA para atender aos requisitos de desempenho. Esta solução, no entanto, apresenta novos desafios em relação aos requisitos de confiabilidade. Particularmente para FPGAs baseados em SRAM, soft errors na memória de configuração são uma ameaça de confiabilidade significativa. Neste trabalho, apresentamos um mecanismo de tolerância a falhas abrangente para lidar com falhas de configuração na funcionalidade de módulos de avaliação de expressões regulares baseados em FPGA. Além disso, é introduzido um mecanismo de correção de erros que considera o posicionamento desses módulos no FPGA para reduzir o tempo de reparo do sistema, melhorando a confiabilidade e a disponibilidade. Os resultados experimentais mostram que a taxa de falha geral e o tempo de reparo do sistema podem ser reduzidos em 95% e 90%, respectivamente, com custos de área e performance admissíveis. / The Network Function Virtualization (NFV) paradigm promises to make computer networks more scalable and flexible by decoupling the network functions (NFs) from dedicated and vendor-specific hardware. However, network and compute intensive NFs may be difficult to virtualize without performance degradation. In this context, Field-Programmable Gate Arrays (FPGAs) have been shown to be a good option for hardware acceleration of virtual NFs that require high throughput, without deviating from the concept of an NFV infrastructure which aims at high flexibility. Regular expression matching is an important and compute intensive mechanism used to perform Deep Packet Inspection, which can be FPGA-accelerated to meet performance constraints. This solution, however, introduces new challenges regarding dependability requirements. Particularly for SRAM-based FPGAs, soft errors on the configuration memory are a significant dependability threat. In this work we present a comprehensive fault tolerance mechanism to deal with configuration faults on the functionality of FPGA-based regular expression matching engines. Moreover, a placement-aware scrubbing mechanism is introduced to reduce the system repair time, improving the system reliability and availability. Experimental results show that the overall failure rate and the system mean time to repair can be reduced in 95% and 90%, respectively, with manageable area and performance costs.

No description available.

Der exponentielle Anstieg elektronisch gespeicherter Daten erfordert leistungsfähige Systeme zur Verarbeitung und Analyse großer Datenmengen. Parallel relationale Datenbanksysteme (PRDBMS) waren lange Zeit der Standard für analytische Abfragen. Neuere Systeme, wie Apache Flink, Tez und Spark, nutzen erweiterte Ansätze zur Analyse und trennen logische Spezifikationen von physischen Ausführungen. Ein weit verbreitetes Optimierungsverfahren in der analytischen Verarbeitung ist die partielle Aggregation, bei der Aggregation in zwei Stufen erfolgt: Zunächst werden partielle Aggregatgruppen erstellt, die dann zusammengeführt werden, um das Endergebnis zu berechnen. Dieses Verfahren ermöglicht eine parallele Verarbeitung und reduziert die Größe der Zwischenergebnisse. Bisherige Ansätze konzentrieren sich auf ordnungsunabhängige Gruppierungsfunktionen, bei denen Elemente ohne Berücksichtigung der Reihenfolge gruppiert werden können. In der Praxis gibt es jedoch auch ordnungsabhängige Gruppierungsfunktionen, die von der Reihenfolge der Eingaben abhängen und komplexer in der parallelen Ausführung sind. Derzeit existieren nur begrenzte Ansätze für eine effiziente Parallelisierung solcher Funktionen. Diese Dissertation präsentiert einen neuen Ansatz zur Parallelisierung von Aggregationsanfragen für drei ordnungsabhängige Gruppierungsfunktionen: Sessionization, Regular Expression Matching (REM) und Complex Event Recognition (CER). Unsere Methode nutzt zerlegbare Aggregationsfunktionen, um eine effiziente parallele Ausführung in modernen Shared-Nothing-Compute-Umgebungen zu ermöglichen. Die stufenweise Ausführung dieser Funktionen eröffnet neue Optimierungsmöglichkeiten. Unser Ansatz erlaubt es Optimierungsalgorithmen, zwischen sequentiellen und stufenweisen Verfahren zu wählen. Zusätzlich schlägt die Arbeit ein Schema vor, wie weitere Gruppierungsfunktionen zerlegt und in die partielle Aggregation integriert werden können. / Advances in information technologies and decreasing cost for storage and compute capacities lead to exponential growth of data being available electronically worldwide. Systems capable of processing these large amounts of data with the goal of analyzing and extracting information are essential for both: research and businesses. Analytical data processing systems employ various optimizations to execute queries efficiently. Partial Aggregation (PA) using GroupBy and decomposable aggregation functions is a common optimization approach in analytical query processing. Analytical systems execute PA in two stages: During the first stage, they create partial groups to compute partial aggregates. During the second stage, the partial aggregates are grouped and aggregated again to produce the final result. The main benefits of PA are an increased potential of parallel execution during the first stage and a reduction of intermediate result sizes by aggregating over the partial groups. So far, existing approaches to PA only use an order-agnostic grouping function on sets to create groups. There are grouping functions that depend on ordered input and information on previously processed input items to associate a given input item to its group. Staged execution of order-dependent grouping functions is more difficult than for order-agnostic grouping functions. Systems must compute correct partial states during the first stage and combine them during the final stage. Approaches for efficient parallel execution only exist in a limited way despite the high practical relevance. In this thesis, we present a novel approach for parallelizing aggregation for three order-dependent grouping functions: Sessionization, Regular Expression Matching (REM), and Complex Event Recognition (CER). Our approach of computing the three grouping functions in stages combined with decomposable aggregation functions allows for efficient parallel execution in state-of-the-art shared-nothing compute environments.