Distributed and Iterative Souping for Graph Neural Networks

cpre 550

For this project, I presented a novel approach to distributed GNN training based on the ideas presented in Model Soups and Graph Ladling papers. My approach involved iteratively training and souping a Graph Neural Network in a distributed fashion. My distributed souping algorithm led to a significant speedup with multiple devices over the baseline, and my iterative approach led to a significant gain in accuracy at the cost of some extra time training. 

model parallelism for Graph neural networks

cpre 525

In this project, I experimented with model parallelism for Graph Neural Networks. By spreading GNN layers across multiple GPUs, I was able to significantly reduce single-GPU memory usage, allowing for the use of larger graphs and models, at the cost of the extra time required to move tensors between devices. In the case of the Reddit dataset, I even observed a decrease in the time taken to train.

I also attempted to implement true pipeline parallelism (like presented in GPIPE) for Graph Neural Networks, but as discussed in previous works, this version of pipeline parallelism is infeasible for GNNs, and I my implementation did introduce a significant time penalty as expected.

Real-time scheduling on cybot

cpre 558

CPRE 558 introduced the concepts of real-time systems and real-time scheduling algorithms, so for my term project, my group chose to implement real-time scheduling on a real robot-vacuum (termed CyBots for their use to teach embedded systems programming at Iowa State). We were able to do so by installing FreeRTOS onto the robot with system modifications and implementing custom routines which manipulate the priority of tasks in the system.

Our tasks consisted of real-world tasks that a robot vacuum would be expected to do (turn, drive forward, scan, etc.). We implemented both the EDF and RM scheduling algorithms, and evaluated their performance across numerous scenarios. We did this by measuring both task latency and the number of tasks which missed their deadlines, and we were able to verify what we learned in class about the scheduling algorithms through our experiments. 

Semantic Visit Aware Recommendation of Hotels

Senior Design Project

For my senior design project, my team members and I were assigned to add to the work of a graduate student who developed algorithms to recommend Points of Interest (PoI) in a Geographical Information System (GIS). The algorithm takes in the current location of the user, and depending on the intended application, will recommend a set of diverse PoI that is traversable using a relatively short path from the user’s starting location.

Our task as a senior design team is to create an application that can display GIS data and could be used by a potential customer. We are to then use this application, along with a large set of GIS data, to demonstrate the strengths and weaknesses of recommendation algorithms.

From this project, I expect to learn a lot about GIS systems and programming. I also plan to gain more experience with backend work. I will also get to work on a project with a much larger team (my senior design team has 7 students), which should teach me a lot about working in a larger development environment. We plan to split into smaller teams that will operate on their sprint cycles, which will also be educational.

I hope that our work on this project will contribute to the body of knowledge on GIS-based recommendation systems and that we can demonstrate some interesting use cases of these algorithms.

Exploring the Use of Local Search in Political Districting and its Applications to Congressional Redistricting in the State of Iowa

cpre 572

This work employed well known local search algorithms for the task of congressional redistricting. In order to use the algorithms for redistricting I used open source geographical data to gather the shapes and locations of all counties. I was then able to create a useful graph of Iowa’s 99 counties by determining bordering counties and excluding corner-to-corner borders. To generate a districting for these counties, I needed to follow a number of rules and heuristics. First, districts must be contiguous. Next, districts must balance compactness and population equality. 

Originally, I attempted randomly coloring the graph node-by-node, but the number of contiguous districtings are an extremely small set compared to the number of possible colorings of the graph. So, instead I employed two unique algorithms to randomly generate a set of contiguous districts. From these pseudo-random districtings, I initiated local search. I evaluated various local search algorithms: steepest ascent hill climbing, stochastic hill climbing, and simulated annealing.

From this project, I learned a lot about applied graph theory and local search algorithms. It also introduced me to research, and I read several papers (both on political districting and local search algorithms). It is one of my favorite projects to-date.

Designing a GPU

CPRE 480

In CPRE 480: Graphics Processing and Architecture, we spent the semester designing our own GPUs. To do this, we were not only responsible for writing the individual steps of the Graphics Pipeline in VHDL but also for writing some of the driver code (in C), and for writing OpenGL test programs (in C) to test our GPU. Our VHDL code was then deployed onto an FPGA using Vivado, allowing us to see our results on real hardware.

Each group in class was responsible for designing their own graphics pipeline, piece by piece. We began by designing our input assembler to keep track of vertices, and our viewport module to calculate their positions in screen space. Over the course of the semester, we added a rasterizer, a vertex shader, a fragment shader, and implemented color blending. Each team then chose their own addition to the GPU as a final project; my group chose to implement texturing.

My role in the project was flexible throughout the semester. I occasionally wrote the OpenGL code, sometimes helped with the driver, but eventually settled into writing and testing most of the VHDL.

From this project, I learned much about digital hardware design and verification using VHDL and an FPGA. I also became much more skilled at writing clear, understandable, but efficient VDHL. Lastly, I learned an incredible amount about graphics processing and gained some experience with writing driver code.

Mobile App Development

CPRE 186, CS 309

In CPRE 186, we were tasked with working on a project for the semester. My group chose to create a mobile app in Dart using Flutter on Android Studio. This allowed us to test our app on both Android and IOS emulators, and even deploy our app onto both kinds of devices. Our mobile app was a collection of fun games that we each developed separately, then integrated into the final application. Our games included: minesweeper, rock paper scissors, coin-flip, and tap-game (a cookie-clicker-esque battle game). For 186, my role was to create the main interface for the application (including settings menus, game stats, etc.). I also wrote rock paper scissors and coin-flip.

In CS 309, I continued my adventure with mobile app development. My group’s project for CS 309 was to develop PetMash, a cute-and-fuzzy version of Mark Zuckerberg’s FaceMash with a few extra features (notably, the ability to create accounts for pets and humans, an interactive like history, and a leaderboard for the cutest pets). We developed our app in Java and XML on Android Studio, with a backend in MySQL. My role was frontend development and testing, but I also took a leadership role in assigning tasks and designing the API where frontend met backend. 

Both of these courses and mobile development projects taught me an incredible amount about the software development workflow. For both projects, we used Git for versioning, and for CS 309 we also used Git for code reviews. In addition to learning how to do that I also got experience with scrum, gained lots of knowledge about backend, worked with websockets, and learned about software development life cycles.

Overwatch Tryouts Matchmaker

Gaming and Esports club

As esports manager for Overwatch at Iowa State’s Gaming and Esports Club I am responsible for hosting tryouts and assigning players to teams every semester. Tryouts can often be a stressful experience, even when I get help from alumni and fellow players. This is because Overwatch is a complex team game: with 6 players per team, each player playing a different role. When confronted with a list of 15-30 tryouts, all with different ranks and preferred roles, it can be very difficult to assign players to teams they fit in and have them play against each other in a way that allows us to judge players fairly.

To solve this problem, and to gain some experience with GUI programming on Windows, I built an interactive program in Java using the JPanel Library. The program takes as input a list of players (including their preferred roles and ranks) that can either be entered manually or imported from a file. The list of players can also be saved as a file for future use. Each player’s ranks and preferred roles can be adjusted in real time. The program will generate two random teams with all players playing their desired roles and the teams being extremely close in skill level. A secondary mode also allows the program to generate a set of “highest ranked” rosters (maximizing the rank of a team of 6, then finding the next-highest average ranked team of 6, and so on). 

I have been using the program to conduct tryouts for the past year and a half, and it has been a resounding success. I am able to generate matchups quickly that players are happy with, and I can spend more time evaluating player’s skill levels for their placement on our teams.

This project taught me a ton about GUI programming and optimizing algorithms in Java (the initial algorithm took an incredibly long amount of time to run, but I’ve improved it so that the program generates teams instantly).