The present master’s dissertation had as subjects matter the Sport and Leisure Program of City – Traditional People and Communities – Quilombolas and Rural of University Federal of Santa Maria (SLPC/TPC/UFSM) and initial education of teacher of Physical Education and Sport Centre (UESC) of institution concerned. The research aimed to understand how acting experience as social agents at SLPC/PCT/UFSM reverberated in initial education of Physical Education academics of UESC/UFSM. The justification has emerged of questions observed as integrant of Program management team, against intricacies faced by academics that yet in training process, would recruit study periods and meeting between themselves and with project coordination, in perspective to heal difficulties, to look for knowledge and consequently to qualify actions as social agents in communities involved. Methodological ways has characterized by a qualitative research as study of case, using semi-structured interviews as instrument for getting of searches sources with five participating academics of study and content analysis method (Franco, 2012) to analyse them. Through of this method, we found five categories: the choice of Physical Education course; initial education at Physical Education course of PEDC/FUSM; Quilombolas and rural communities; regent activities of social agents’ routine of SLPC/TPC and action legacies at SLPC/TPC/FUSM front initial education in Physical Education of PESC/FUSM. This way for concluding, even in the light of the points, which exhibited different ways of repercussion front initial education at PE of these academics, the view besides academic world is necessary. Because even these points has been relevant contributions for initial education, the inserts in SLP/TPC/FUSM also corroborate with learnings about to live in community, respect to diversity, overcoming adversity and to provide to these people that understanding their rights of citizens. / A presente dissertação de mestrado teve como suas temáticas de estudo o Programa Esporte e Lazer da Cidade - Povos e Comunidade Tradicionais - Quilombolas e Rurais da Universidade Federal de Santa Maria (PELC/PCT/UFSM) e a formação inicial de professores do Centro de Educação Física e Desportos (CEFD) da referida instituição. E teve por objetivo buscar compreender de que modo a experiência de atuação como agentes sociais no PELC/PCT/UFSM repercutiu na formação inicial dos acadêmicos de Educação Física do CEFD/UFSM. A justificativa emergiu das questões observadas enquanto integrante da equipe gestora do Programa, frente aos meandros enfrentados pelos acadêmicos que ainda em processo de formação, recrutavam períodos de estudos e encontros entre eles próprios e com a coordenação do projeto, na perspectiva de sanar dificuldades, buscar conhecimentos e consequentemente qualificar as atuações como agentes sociais nas comunidades envolvidas. Os caminhos metodológicos se caracterizaram por meio de uma pesquisa de cunho qualitativo do tipo estudo de caso, utilizando as entrevistas semiestruturadas como instrumento para obtenção das fontes de pesquisa com os cinco acadêmicos participantes do estudo e o método de analise de conteúdo (Franco, 2012) para analisa-las. E através do referido método, chegou-se a cinco categorias: A escolha do curso de Educação Física; A formação inicial no Curso de Educação Física do CEFD/UFSM; As comunidades quilombolas e rurais; As atividades regentes da rotina dos agentes sociais do PELC/PCT/UFSM e Legados da atuação no PELC/PCT/UFSM frente a formação inicial em Educação Física do CEFD/UFSM. De modo a concluir, que mesmo mediante os pontos apresentados que esporam diversos modos de repercussão frente a formação inicial em EF destes acadêmicos, o olhar além do mundo acadêmico se faz relevante. Pois mesmo que estes pontos tenham sido contribuições relevantes à formação inicial, as inserções no PELC/PCT/UFSM também corroboraram com os aprendizados sobre viver em comunidade, o respeito a diversidade, a superação de adversidades e proporcionar a estas pessoas que conheçam seus direitos de cidadãos.

Relational database systems provide various services and applications with an efficient means for storing, processing, and retrieving their data. The performance of these systems has a direct impact on the quality of service of the applications that rely on them. Therefore, it is crucial that database systems are able to adapt and grow in tandem with the demands of these applications, ensuring that their performance scales accordingly. In the past, Moore's law and algorithmic advancements have been sufficient to meet these demands. However, with the slowdown of Moore's law, researchers have begun exploring alternative methods, such as application-specific technologies, to satisfy the more challenging performance requirements. One such technology is field-programmable gate arrays (FPGAs), which provide ideal platforms for developing and running custom architectures for accelerating database systems. The goal of this thesis is to develop a domain-specific architecture that can enhance the performance of in-memory database systems when executing analytical queries. Our research is guided by a combination of academic and industrial requirements that seek to strike a balance between generality and performance. The former ensures that our platform can be used to process a diverse range of workloads, while the latter makes it an attractive solution for high-performance use cases. Throughout this thesis, we present the development of a system-on-chip for database system acceleration that meets our requirements. The resulting architecture, called CbMSMK, is capable of processing the projection, sort, aggregation, and equi-join database operators and can also run some complex TPC-H queries. CbMSMK employs a shared sort-merge pipeline for executing all these operators, which results in an efficient use of FPGA resources. This approach enables the instantiation of multiple acceleration cores on the FPGA, allowing it to serve multiple clients simultaneously. CbMSMK can process both arbitrarily deep and wide tables efficiently. The former is achieved through the use of the sort-merge algorithm which utilizes the FPGA RAM for buffering intermediate sort results. The latter is achieved through the use of KeRRaS, a novel variant of the forward radix sort algorithm introduced in this thesis. KeRRaS allows CbMSMK to process a table a few columns at a time, incrementally generating the final result through multiple iterations. Given that acceleration is a key objective of our work, CbMSMK benefits from many performance optimizations. For instance, multi-way merging is employed to reduce the number of merge passes required for the execution of the sort-merge algorithm, thus improving the performance of all our pipeline-breaking operators. Another example is our in-depth analysis of early aggregation, which led to the development of a novel cache-based algorithm that significantly enhances aggregation performance. Our experiments demonstrate that CbMSMK performs on average 5 times faster than the state-of-the-art CPU-based database management system MonetDB.:I Database Systems & FPGAs 1 INTRODUCTION 1.1 Databases & the Importance of Performance 1.2 Accelerators & FPGAs 1.3 Requirements 1.4 Outline & Summary of Contributions 2 BACKGROUND ON DATABASE SYSTEMS 2.1 Databases 2.1.1 Storage Model 2.1.2 Storage Medium 2.2 Database Operators 2.2.1 Projection 2.2.2 Filter 2.2.3 Sort 2.2.4 Aggregation 2.2.5 Join 2.2.6 Operator Classification 2.3 Database Queries 2.4 Impact of Acceleration 3 BACKGROUND ON FPGAS 3.1 FPGA 3.1.1 Logic Element 3.1.2 Block RAM (BRAM) 3.1.3 Digital Signal Processor (DSP) 3.1.4 IO Element 3.1.5 Programmable Interconnect 3.2 FPGADesignFlow 3.2.1 Specifications 3.2.2 RTL Description 3.2.3 Verification 3.2.4 Synthesis, Mapping, Placement, and Routing 3.2.5 TimingAnalysis 3.2.6 Bitstream Generation and FPGA Programming 3.3 Implementation Quality Metrics 3.4 FPGA Cards 3.5 Benefits of Using FPGAs 3.6 Challenges of Using FPGAs 4 RELATED WORK 4.1 Summary of Related Work 4.2 Platform Type 4.2.1 Accelerator Card 4.2.2 Coprocessor 4.2.3 Smart Storage 4.2.4 Network Processor 4.3 Implementation 4.3.1 Loop-based implementation 4.3.2 Sort-based Implementation 4.3.3 Hash-based Implementation 4.3.4 Mixed Implementation 4.4 A Note on Quantitative Performance Comparisons II Cache-Based Morphing Sort-Merge with KeRRaS (CbMSMK) 5 OBJECTIVES AND ARCHITECTURE OVERVIEW 5.1 From Requirements to Objectives 5.2 Architecture Overview 5.3 Outlineof Part II 6 COMPARATIVE ANALYSIS OF OPENCL AND RTL FOR SORT-MERGE PRIMITIVES ON FPGAS 6.1 Programming FPGAs 6.2 RelatedWork 6.3 Architecture 6.3.1 Global Architecture 6.3.2 Sorter Architecture 6.3.3 Merger Architecture 6.3.4 Scalability and Resource Adaptability 6.4 Experiments 6.4.1 OpenCL Sort-Merge Implementation 6.4.2 RTLSorters 6.4.3 RTLMergers 6.4.4 Hybrid OpenCL-RTL Sort-Merge Implementation 6.5 Summary & Discussion 7 RESOURCE-EFFICIENT ACCELERATION OF PIPELINE-BREAKING DATABASE OPERATORS ON FPGAS 7.1 The Case for Resource Efficiency 7.2 Related Work 7.3 Architecture 7.3.1 Sorters 7.3.2 Sort-Network 7.3.3 X:Y Mergers 7.3.4 Merge-Network 7.3.5 Join Materialiser (JoinMat) 7.4 Experiments 7.4.1 Experimental Setup 7.4.2 Implementation Description & Tuning 7.4.3 Sort Benchmarks 7.4.4 Aggregation Benchmarks 7.4.5 Join Benchmarks 7. Summary 8 KERRAS: COLUMN-ORIENTED WIDE TABLE PROCESSING ON FPGAS 8.1 The Scope of Database System Accelerators 8.2 Related Work 8.3 Key-Reduce Radix Sort(KeRRaS) 8.3.1 Time Complexity 8.3.2 Space Complexity (Memory Utilization) 8.3.3 Discussion and Optimizations 8.4 Architecture 8.4.1 MSM 8.4.2 MSMK: Extending MSM with KeRRaS 8.4.3 Payload, Aggregation and Join Processing 8.4.4 Limitations 8.5 Experiments 8.5.1 Experimental Setup 8.5.2 Datasets 8.5.3 MSMK vs. MSM 8.5.4 Payload-Less Benchmarks 8.5.5 Payload-Based Benchmarks 8.5.6 Flexibility 8.6 Summary 9 A STUDY OF EARLY AGGREGATION IN DATABASE QUERY PROCESSING ON FPGAS 9.1 Early Aggregation 9.2 Background & Related Work 9.2.1 Sort-Based Early Aggregation 9.2.2 Cache-Based Early Aggregation 9.3 Simulations 9.3.1 Datasets 9.3.2 Metrics 9.3.3 Sort-Based Versus Cache-Based Early Aggregation 9.3.4 Comparison of Set-Associative Caches 9.3.5 Comparison of Cache Structures 9.3.6 Comparison of Replacement Policies 9.3.7 Cache Selection Methodology 9.4 Cache System Architecture 9.4.1 Window Aggregator 9.4.2 Compressor & Hasher 9.4.3 Collision Detector 9.4.4 Collision Resolver 9.4.5 Cache 9.5 Experiments 9.5.1 Experimental Setup 9.5.2 Resource Utilization and Parameter Tuning 9.5.3 Datasets 9.5.4 Benchmarks on Synthetic Data 9.5.5 Benchmarks on Real Data 9.6 Summary 10 THE FULL PICTURE 10.1 System Architecture 10.2 Benchmarks 10.3 Meeting the Objectives III Conclusion 11 SUMMARY AND OUTLOOK ON FUTURE RESEARCH 11.1 Summary 11.2 Future Work BIBLIOGRAPHY LIST OF FIGURES LIST OF TABLES