Nathaniel Kell ‘13
So it is not surprising that the computer science and mathematics double major, and Academic All-American defensive lineman for the Big Red football squad, opted to tackle a vexing open problem in theoretical computer science for his senior research project.
Nat’s problem involved figuring out how to efficiently schedule a sequence of data-intensive jobs on a multicore computer. Each of these jobs is malleable in the sense that it can be configured to use any number of the available processing cores. Ideally, we might expect a malleable job to always run faster if we assign more cores to it. However, in a real system, some amount of overhead time is required to manage each job and share information among the cores. So the amount of time required for a malleable job to run depends on both of these factors. Given a sequence of malleable jobs, we want to efficiently assign a number of cores to each so that the jobs finish as quickly as possible.
Unfortunately, this turns out to be a very hard problem, especially if we must make each decision on the fly without knowing what is coming next. But Nat was able to design a complex algorithm that improved upon the best previously known algorithm, and prove that it is the best that anyone can do! Nat and Dr. Havill submitted their work for publication in the Journal of Scheduling.
Before he graduated in 2013, Nat’s work earned him some impressive honors. At Denison, he was awarded the President’s Medal, the highest honor bestowed upon a student. Nationally, Nat was one of only ten computer science majors to receive a 2012 Barry Goldwater Scholarship. And as a senior, he was awarded an Honorable Mention in the NSF Graduate Research Fellowship competition. Nat is now pursuing a Ph.D. in computer science at Duke University.