Geração de horários usando GPUs

Ao longo de um ano académico, instituições de educação têm a necessidade de gerar centenas de diferentes horários, esta tarefa complexa aloca uma grande quantidade de tempo e de recursos humanos.No passado, a geração de horários era feita manualmente, nos dias de hoje com o aumento da sua complexidade, esta tarefa é realizada por software especializado o que permite reduzir tempo e custos. Uma GPU, é um componente de hardware muito capaz que apresenta dois pontos fortes: largura de banda na memória (GB/s) e poder computacional (GFLOPS), a maioria dos problemas complexos encaixam nestas categorias e a geração de horários não é excepção.O software de geração de horários nem sempre tira vantagem das capacidades do hardware para executar operações paralelas, esta dissertação tem como objetivo explorar as capacidades das GPUs de forma a provar o conceito de uma ou mais implementações simplificadas.É ainda esperado que usando GPUs para resolver este problema, o tempo necessário de computação seja reduzido substâncialmente comparado com as implementações em CPU com um ou mais threads.Throughout an academic year, educational institutions need to generate hundreds of different timetables, this complex task demands a considerable amount of time and human resources.In the past, timetable generation was handmade, in current days as this task complexity increases, it is performed by specialized software which allows to reduce time and costs.Since nearly 10 years ago, single core performance has stopped because it became unfeasible for manufacturers due heat generation and power consumption, in order to achieve higher performance each core frequency was reduced while number of cores were increased.A GPU, is a very capable piece of hardware, it has two particular strengths: memory bandwidth (GB/sec) and raw power (GFLOPS), most of the complex and difficult computational problems fall into these categories and timetable generation problem is no exception.Timetable generation software doesn't always takes advantage of hardware capabilities to perform parallel computations, this dissertation aims to explore GPU's capabilities in order to prove the concept of one or more possible parallel simplified implementations. It is expected that using GPU's to solve this problem the amount of computation time would be reduced substantially compared with CPU implementations in single or multithread