Synthesis of GPU Programs from High-Level Models

Modern graphics processing units (GPUs) provide high-performance general purpose computation abilities. They have massive parallel architectures that are suitable for executing parallel algorithms and operations. They are also throughput-oriented devices that are optimized to achieve high throughput for stream processing. Designing efficient GPU programs is a notoriously difficult task. The ForSyDe methodology is suitable to ease the difficulties of GPU programming. The methodology encourages software development from a high level of abstraction and then transforming the abstract model to an implementation through a series of formal methods. The existing ForSyDe models support the synchronous data flow (SDF) model of computation (MoC) which is suitable for modeling stream computations and is good for synthesizing efficient stream processing programs. There also exists high-level design models named parallel patterns that are suitable to represent parallel algorithms and operations. The thesis studies the method of modeling parallel algorithms using parallel patterns, and explores the way to synthesize efficient OpenCL implementation on GPUs for parallel patterns. The thesis also tries to enable the integration of parallel patterns into the ForSyDe SDF model in order to model stream parallel operations. An automation library that helps designing stream programs for parallel algorithms targeting GPUs is purposed in the thesis project. Several experiments are performed to evaluate the effectiveness of the proposed library regarding implementations of the high-level model.Moderna grafikbehandlingsenheter (GPU) tillhandahåller högpresterande generella syftes-beräkningsförmågor. De har massiva parallella arkitekturer som är lämpliga för att utföra parallella algoritmer och operationer. De är också streaminriktade enheter som är optimerade för att uppnå hög streaming för streamingbehandling. Att utforma effektiva GPU-program är en notoriskt svårt uppgift. ForSyDe-metoden är lämplig för att underlätta svårigheterna med GPU-programmering. Metodiken uppmuntrar mjukvaruutveckling från en hög nivå av abstraktion för att sedan omvandla den abstrakta modellen till en implementering genom en rad formella metoder. De befintliga ForSyDe-modellerna stöder synkron dataflöde (SDF) modell av beräkning (MoC) som är lämplig för modellering av streaming-beräkningar och är bra för att syntetisera effektiv streaming-bearbetningsprogram. Det finns också högkvalitativa designmodeller som kallas parallella mönster vilka är lämpliga för att representera parallella algoritmer och operationer. Avhandlingen analyserar metoden för modellering av parallella algoritmer med parallella mönster, och utforskar sättet att syntetisera effektiv OpenCL-implementering för GPU för parallella mönster. Avhandlingen försöker även att möjliggöra integration av parallella mönster i ForSyDe SDF-modellen för att modellera streaming parallella operationer. Ett automationsbibliotek som hjälper till att designa stream-program för parallella algoritmer som riktar sig mot GPU:er är avsedda för avhandlingsprojektet. Flera experiment utförs för att utvärdera effektiviteten hos det föreslagna biblioteket avseende implementering av högnivåmodellen