Geração de horários usando GPUs

Abstract

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.