Vulcan, Go, and A Triangle, Part 6

In this part we are going to add support for required device layers and extensions before creating a logical device. The logical device creation process is similar to the instance creation process. Instead of telling Vulkan about our application, we will be telling Vulkan about our device requirements.

This part follows closely with the Vulkan Tutorial. I do push the required extensions checks into the device selection function, but otherwise the steps are similar to Drawing a triangle / Setup / Logical device and queues.

Vulcan, Go, and A Triangle, Part 5

In this part I am going to create an object for keeping track of our physical device, enumerate over physical devices, and select a physical device for our application.

I deviate from the vulkan tutorial here a little bit because I wanted to encapsulate physical device related functionality in a specific class. This will become more useful later when dealing with memory buffers. I also create the surface in a different order.

This part relates to Drawing a triangle / Setup / Physical devices and queue families in the original tutorial.

Vulcan, Go, and A Triangle, Part 4

In this part of the tutorial, I'm going to inspect what extensions and layers are available for an instance. The call to vk.CreateInstance can result in vk.ErrorLayerNotPresent or vk.ErrorExtensionNotPresent according to the Vulkan spec. By inspecting the available options and checking if my required options are supported, I can provide a more debuggable error response.

Following the Vulkan Tutorial, I implemented the necessary functions to enumerate over available layers and extensions before calling CreateInstance. This part relates to Drawing a triangle / Setup / Instance / Checking for extension support in the original tutorial.

Vulcan, Go, and A Triangle, Part 3

In this part of the tutorial, we are going to initialize a vulkan instance. The vulkan instance is the connection between your application and the Vulkan framework. It allows the application to enumerate physical devices and supported functionality.

This part relates to Drawing a triangle / Setup / Instance in the original tutorial.

Vulcan, Go, and A Triangle, Part 2

In the last part, we started with adding dependencies, helper functions and the basic skeleton. In this part we are going to start expanding on setup(), cleanup(), and mainLoop().

Each part going forward will end with code that should build and run, although in many cases there will not be a visible output.

Part 2 roughly translates to the second half of Drawing a triangle / Setup / Base code.

Vulcan, Go, and A Triangle, Part 1

This tutorial follows my personal execution of the Vulkan tutorial, with the distinction of being in Go instead of C++.

I started this effort because Go is my preferred programming language and I was interested in understanding more about the modern landscape of GPU programing. While I was able to find a Vulkan tutorial translated for Rust, I could not find an existing one for Go.

While my exploration of Vulkan follows the general approach of the Vulkan Tutorial, I have done certain steps out of order and try to leverage Go idioms where I can. I also tried to write the code so that most steps start with pseudo-code comments which eventually get expanded into code-blocks.

Knapsack and Go

I've been playing around with Go a lot the past year. I've done a couple of projects for pay, and a couple of projects for fun. I have been finding it an incredibly useful pocket language for solving almost any problem.

Recently, I spent some time researching the different solutions to the knapsack problem. After reading all about the knapsack problem on wikipedia, I implemented the bounded solutions in go. As a control, I used the item list for Nils Haldenwang's post about Genetic Algorithm vs. 0-1-KNAPSACK.

I started off with a recursive brute force approach, and kept evolving that approach until I had an iterative solution that used a channel for generating the set of combinations. It probably isn't the most efficient way to implement the set generation, but I still tend to throw channels and goroutines at any generator I see in code.

After I had the brute force approach, I optimized it a little bit by trimming out branches that would never be used. This resulted in about half the time required for the same dataset. But it actually doesn't change the worst case scenario much. It isn't so much of a solution as an optimization that makes it look a little more breadth first search. These ran in about 17 seconds for brute force, and 12 seconds for the optimized version.

Then I implemented the dynamic programming approach, which is just unbeatable speed wise. Didn't even register as a millisecond for the testing dataset. It took me a little bit to understand how to discover the list of items packed in the knapsack, but the total solution was still small enough to understand. I used Mike's Coderama to help me understand what was going on there.

Finally, I implemented the meet in the middle solution. This was actually a surprisingly faster solution than I expected. The code was able to reuse the parts I had done for the brute force solution, which made it fast to write. The simple solution was able to solve the 24 item problem in about 100ms. I played around with it a bit to optimize the best-case scenarios, and got it to about 40ms on average.

In the end, I like the meet in the middle solution the best. It is feasible to use the solution for all types of bounded knapsack problems where you have to use a float for the weight. I posted my go implementation of the bounded knapsack problem on gist.

Now, its time to play with the bin packing problem.