Grant: Discovery Grants Program - Individual

The long term objective of my research is to use computers to solve open problems related to the existence and enumeration of combinatorial objects. One characteristic of this type of research is that it often requires a large amount of computing, something equivalent to using hundreds of computers over months or years. Since the mid 1990's, computers found in typical university teaching laboratories provide the most cost-effective computing environment. One can just use these computers for research purposes when no students are using them, such as during the overnight hours. However, this fortunate situation is changing. As the price of computer drops, more and more students are buying their own laptops. Universities are starting to cut back on general computing facilities that students do not need, and moving towards a model of providing fewer computers but with higher-end models that students normally do not have access to, in order to complement their learning experience. The net result, for the researchers, is that we have access to fewer but more powerful computers. These high end computers typically have multi-core CPU's, and have powerful graphics processors. While it is easy to effectively use the multi-core CPU's, using the graphics processors effectively is not as simple.My research work divides naturally into two parts: developing tools, and using tools to solve problems. It is time to do some tool development. My short term objective is to develop algorithms for enumerating combinatorial objects that can be run effectively on massively parallel graphics processors. I will work on Nvidia graphics devices, which uses the SIMT (Single Instruction Multiple Thread) model. I will draw on my earlier experience of programing a CRAY (a vector computer) and a Connection Machine (a SIMD machine). After developing these algorithms, I will continue my long term objective and work on the many open questions related to the existence and enumeration of combinatorial objects.