When it comes to scoring the National Science Foundation’s (NSF) CAREER awards, WUSTL’s School of Engineering & Applied Science has the hot hand.
Since 2005, 12 engineering faculty have received a CAREER award, including nine of the 20 faculty in the Department of Computer Science & Engineering.
A bellwether of outstanding young faculty, CAREER recognition provides “support of the early career-development activities of those teacher-scholars who most effectively integrate research and education within the context of the mission of their organization” with the goal of “building a firm foundation for a lifetime of integrated contributions to research and education.”
Two of the latest WUSTL CAREER winners are computer scientists who are making innovative contributions to enable faster, more complex computation that will improve a host of applications from high-level research to routine consumer uses and machine learning. This machine learning includes the imparting of artificial intelligence to computers so that they learn from repeated trials, errors and successes. Both engineers traffic in algorithms, detailed mathematical formulas that encode a sort of recipe for computer programs to carry out.
Kunal Agrawal, PhD, assistant professor of computer science & engineering, writes algorithms for platforms that will allow programmers to easily write correct and efficient complex parallel programs. Kilian Q. Weinberger, PhD, assistant professor of computer science & engineering, as part of his research creates algorithms that can compare individual texts, images or sounds. His algorithms seek to help determine whether two types of data are similar or dissimilar, enabling cancer researchers, for instance, to pinpoint exactly where a tumor (a dissimilar image on an MRI scan) ends and healthy tissue (similar) begins. Agrawal and Weinberger are occasional collaborators. Agrawal is using her algorithms for parallel computing to make training of Weinberger’s machine learning algorithms faster so that a Google or Yahoo search of a breaking news event, for instance, can be found with unprecedented speed.
Scheduling of streaming applications
Agrawal focuses on parallel computing, which is the use of more than one core, or processor, on a computer to enable snappier applications. Sequential programs execute consecutive and ordered processes, one at a time, on a single core. Parallel programming, in contrast, provides concurrent, simultaneous execution of processes that use multiple cores, breaking down a problem into many parts, all the sub-parts pulling together to solve the problem much more quickly.
All the rage in research circles as far back as 40 years ago, parallel computing hype chilled in the ’90s when chip makers such as Intel made sequential programs go faster by making better and better chips that doubled desktop and laptop speed every 18 months or so. But then about 10 years ago sequential programming hit physical limitations that reined in the great leaps of speed, and parallel programming revived.
Today, a three-year-old laptop typically has two cores, and if you went out tomorrow to buy a new one, it likely would have four. Ambitious plans abound to build computers with many more cores, but if they are built, nobody will come, according to Agrawal, because the programming hasn’t been figured out yet.
“Most programmers only know how to write sequential programs,” she says. “Parallel programs are much harder to write. A lot of my research is about how to build software systems that enable people to write good parallel programs relatively easily. My main thrust is scheduling — which parts of the parallel program should run on which cores and when.”
Agrawal designs schedulers for parallel programs written in a variety of paradigms, such as streaming and dynamic multi-threading, and proves that these schedulers will guarantee good performance to these programs.
Agrawal’s CAREER award focuses on scheduling of streaming applications, which are typically applications designed to process large quantities of data very fast. One component of her research deals with cache-conscious scheduling. Computers contain many levels of memory, some slow and large and others fast and small. To keep things up-tempo, fast memory is much preferred, and Agrawal writes scheduling algorithms that are designed to access fast memory as much as possible and reduce accesses to slow memory. Cache-conscious scheduling is what she calls her approach. Another component of her career proposal is concerned with avoiding deadlock — when programs stop and can’t make progress because different components are waiting on each other.
Yet, another component of her research focuses on resource allocation. “Let’s say you have a machine with 100 cores and you have 10 programs wanting to access them,” she explains. “You can give all of them 10 cores each, but maybe one of these programs is not very parallel at all and will just use one core and waste the other nine. You want to avoid that and give every program the right number of cores that it needs. I have come up with ways of how this can be done for particular systems in the past, and I am working on expanding on it.”
Agrawal teaches an undergraduate course in algorithms that is required for computer science majors and minors and a graduate course in parallel algorithms. She also is involved in K–12 activities with WUSTL’s Science Outreach Program, which is also a component of the CAREER award.
Parallel structure & learning algorithms
While Agrawal’s algorithms are about timing, speed and easy access, Weinberger’s are about learning.
“At the very core of machine-learning is the question: What is similarity?” he says. “If you want to teach a program how to identify your sister-in-law, you enter her picture into the computer and it now knows what similarity means in a human context. It will then look for similar pictures.”
Weinberger’s CAREER activities involve designing algorithms for computers that enable them to capture automatically the difference between similarity and dissimilarity. His learning algorithms make no assumption of application, and thus are general, and can be used in visual, audio or textual media. One project he has is to improve the ranking behavior of search engines. Weinberger sought Agrawal’s expertise in this regard by making his learning algorithms parallel.
“Speed is very important here,” says Weinberger. “Remember the overnight singing sensation, Susan Boyle? No one had ever heard the name. But search engines went crazy after she created a stir. In the ranking project I’m looking to provide algorithms that can be retrained very, very quickly so that they can be updated and deliver the best Web pages. Parallel structure is made for this.”
In the biomedical realm, Weinberger is collaborating with Daniel Moran, PhD, WUSTL associate professor of biomedical engineering, and Eric Leuthardt, MD, WUSTL associate professor of neurological surgery at the School of Medicine. Together, their efforts aim to eventually provide a transplanted artificial or real arm that can act upon brain neuronal activity and perform tasks that the brain tells it to. Weinberger’s learning algorithms in this instance learn to read directions that the neurons from the motor cortex actually provide the limb. It learns which data tell a trigger finger to squeeze, for instance. The idea is to implant a chip or chips bearing Weinberger’s algorithms into the transplanted arm that can make it act naturally.
To do this, Weinberger supplies complex linear algebraic and statistical techniques that actually take untold reams of numerical data and map them into multi-dimensional (3-D and beyond) space to bring similar data together and separate dissimilar data — all so that the algorithm recognizes data it has learned.
“Working with all of these readings is a bit like putting a microphone to New York City and trying to understand what people are talking about,” he explains. “However, we are making significant strides.”
Weinberger’s outreach component for his CAREER award is his effort to make junior and senior high school students aware that mathematics is real and used daily. He says his theme is “From Algebra to Google,” and he hopes to show students the mathematics behind daily searches and other applications.
Weinberger teaches Machine Learning and Introduction to Artificial Intelligence, graduate courses that some undergrads also can take. In the latter course (an adaptation from UC-Berkeley), a requirement this past spring was to implement learning algorithms for a Pac-Man game, “Capture the Flag.” The game involves both Pac-Man and a ghost, and students have to use learning algorithms for both. In early May, in a contest between WUSTL and the University of Maryland, WUSTL won.
“Ours was an all-undergrad team that we’re really very proud of,” Weinberger says.
Tony Fitzpatrick is a freelance writer based in St. Louis.