12/17/2020 Laura Schmitt, Illinois CS 11 min read
A longtime CS faculty member at Illinois (1972-1998), Liu is best known for his foundational and pioneering research in combinatorial mathematics and algorithms, which had applications to real-time systems and electronic design automation.
Written by Laura Schmitt, Illinois CS
Distinguished researcher, educator, university leader, business advisor, and radio host Dave Chung-Laung Liu died on November 7, in Taipei, Taiwan. He was 86.
A longtime CS faculty member at Illinois (1972-1998), Liu is best known for his foundational and pioneering research in combinatorial mathematics and algorithms, which had applications to real-time systems and electronic design automation (EDA). His work essentially paved the way for robots, drones, autonomous vehicles, and enabled advances in integrated circuit design.
"The impact of Dave Liu on Illinois CS is impossible to overstate," said Nancy M. Amato (PhD CS '95), Illinois CS Department Head and Abel Bliss Professor of Engineering. "He was here in the early days of computing and helped lay the foundations of what would become one of the top computer science programs in the world. As important as his scientific contributions were, equally important was his role in establishing the collaborative and collegial culture in the department that persists today and permeates all that we do and are."
Added Amato: "While they probably didn't realize it at the time, Dave and his wife, Jane Liu, herself a lauded CS professor, were a power couple long before that term was fashionable and served as formative role models for our growing department. Their trailblazing example paved the way for many more—today, we have 7 academic couples on the faculty in the department—and even more if you count affiliates."
Born in the southern China city of Guangzhou, Liu moved with his family to Macau in 1937 after the Japanese invasion of his homeland. “During the second world war, Macau was the only city that remained neutral in the whole of Southeast Asia,” Liu said in a 2013 oral history interview with the Computer History Museum (CHM). “I actually had a rather quiet, uneventful time because I did not have any direct experience with the war.”
In 1952, he graduated high school and entered the College of Engineering in Taiwan—now known as the National Cheng Kung University—where he studied electrical engineering. In the CHM interview Liu recalled his calculus teacher, who taught his students how to solve a problem in different ways.
“Looking back, I think that is one of the most important lessons to learn,” he said. “How to solve a problem, how to look at a problem from different angles, different perspectives.”
He earned his bachelor’s degree in 1956, served two years in the Taiwanese military, and then enrolled in graduate school at MIT. After earning his master’s degree in CS, he considered taking a job in industry, but instead decided on a career in academia after serving as a teaching assistant for a logic design course.
“Imagine a graduate student from Taiwan, after two years, in the third year [of graduate school], I was handling a course completely on my own—lectures, homework, examinations,” Liu recalled in the CHM interview. “That was a wonderful, wonderful experience.”
Liu completed his doctoral work in 1960 on the structure of finite-state machines under the supervision of professor Dean Arden, who participated in the design of the Whirlwind machine, one of the world’s earliest digital computers.
He joined the MIT faculty and conducted research in the general area of embedded systems design. He created a table-driven compiler as part of Project MAC, a functional time-sharing computer system that became a foundation for modern computer networking and collaboration.
In 1968, he published his first textbook, Introduction to Combinatorial Mathematics, which his former student Jason Cong (PhD CS ’90) described as one of two highly influential books released that year.
“It’s a landmark contribution to computer science because the topics—recurrence relations, graph theory, transport networks, linear and dynamic programming, and trees, circuits and cut-sets—are very important to computing and EDA,” said Cong, the Volgenau Chair for Engineering Excellence at UCLA and National Academy of Engineering member. “This was several years before the concept of NP completeness was introduced.”
According to Cong, Liu had another major contribution with the 1973 publication of a paper he co-authored with James Layland at the Jet Propulsion Laboratory, which was investigating the notion of real-time scheduling for space exploration. Their paper, “Scheduling algorithms for multiprogramming in a hard-real-time environment,” has been cited nearly 12,700 times according to Google Scholar.
“He pioneered scheduling analysis of real-time systems,” said Lui Sha, the Donald B. Gillies Chair in Computer Science at Illinois, noting the 12,000-plus citations is an incredibly large number. “Some papers will get several hundred citations, and if a paper gets 1,000 citations, [the author] would celebrate. The impact of Dave’s paper is still being felt, which means the work has stood the test of time.”
Today, scheduling analysis is critical to the development and implementation of robots, self-driving vehicles, and drones as their software systems examine huge amounts of camera and sensor data simultaneously and then act on the data through steering, changing speed, or other actions.
“All that data has a deadline and scheduling analysis determines if the deadlines can be met,” Sha said.
In 1972, Liu and his wife Jane, an expert in real-time and embedded systems, joined the CS faculty at Illinois. By the early 1980s, Liu expanded his research into EDA.
“The timing was perfect, as this was the beginning of the long exponential growth of the integrated circuit (IC) industry,” said Cong, referring to the 1981 release of IBM’s first PC, which ran on an Intel 8088 microprocessor with 29,000 transistors. “The design complexity quickly outgrew the simple ad hoc EDA algorithms used in the 1970s. The industry needed more efficient EDA algorithms to cope with the exponentially growing design complexity. Liu and his research group provided timely solutions to many important EDA problems as the IC technology and complexity advanced.”
According to Rob Rutenbar, Liu was one of the first researchers to look at EDA problems and mathematically define the components like floorplanning, layout, routing, and timing.
“He led the transformation from ad hoc EDA to algorithmic EDA,” said Rutenbar, senior vice chancellor for Research at the University of Pittsburgh and former head of the Illinois CS department. “I used some of that [knowledge] in a floor planner for my own startup company Neolinear, which was acquired by Cadence in 2004.”
For this work, Liu received the Phil Kaufman Award for Distinguished Contributions to Electronic Design Automation, which is known as the Nobel Prize for the EDA industry.
In 1995, Liu became associate provost at Illinois and served in that position for three years. He retired from Illinois in 1998 and became president of National Tsing Hua University (NTHU), where he left an indelible mark on the campus and education system.
According to the Academia Sinica newsletter, Liu initiated the University System of Taiwan, combining research forces from NTHU with National Chiao Tung University, National Yang-ming University, and National Central University. He also engaged in dedicated fundraising efforts to establish the TSMC building for the new College of Technology Management.
“Overall, he raised more than $700 million during his tenure as president at NTHU,” said Cong.
In 2000, Liu was selected as a member of Academia Sinica, the preeminent academic research institution in Taiwan.
Since returning to Taiwan, Liu was often invited to share his vision, experience, wisdom, and leadership with tech companies, and he made significant contributions to the country’s semiconductor and EDA industries. He served as chairman of the board of TrendForce, a market intelligence provider in the DRAM, LED, LCD, and solar energy tech segments. He was also a board member of numerous companies, including Powerchip Semiconductor, United Microelectronics, MediaTek, Media Tek, and Macronix International.
According to Sha, Liu once said that his father encouraged him to pursue science and engineering in college so he could make a comfortable living, but he was always passionate about the arts.
“When he retired, he had a radio show where he discussed poetry, social sciences, and other topics,” said Sha. “He went back to his first love.”
Beginning in 2005, Liu hosted the weekly radio show, “I love to talk and you love to laugh,” on IC Broadcasting (97.5 FM) in Hsinchu, Taiwan. Entertaining and educational, the show covered a range of topics including, the start of Google, Lincoln and Obama inauguration addresses, poetry and literature, and Steve Jobs’ commencement speech at Stanford.
Liu published three essay collections based on the radio show. One of those collections earned a 2011 book award in the category of popular science.
While at Illinois, Liu advised 26 doctoral students, many of whom became leaders in academia and industry. Andrew Chi-Chih Yao (PhD CS ’75), for example, won the 2000 A.M. Turing Award, considered the Nobel Prize of computing, for his groundbreaking contributions to the theory of computation.
“He taught me how to do research and how to be methodical, rigorous, and intellectually honest, but he also valued human relationships,” said former student Unni Narayanan (PhD CS ’98), an executive at Google, who recalled sitting next to Liu at the Kaufman Award ceremony in 2011. “I had a difficult set back with one of my startups during this time, and here he was about to get this major award. In that moment, he was more concerned about how I was doing. That’s the kind of person he was.”
"Dave was a truly wonderful mentor, teacher, researcher, and life-time friend and role model, and I am forever grateful for the opportunities and advice he gave me over the years,” said Cong who traveled to Taipei in 2018 to spend Father’s Day with Liu. “He was really like a father to me. Unfortunately, that turned out to be our last meeting.”
Rutenbar remembers Liu as a genuinely decent person, who was universally respected and loved. “He was immensely approachable, no pretense, no diva,” Rutenbar said. “He was happy to be a part of this community of people doing great work. He was such a delightful, sunny positive, cheerful person. You wanted to be around Dave.”
Amato recalls how generous Liu was with his time, stepping in to become her de jure advisor when her doctoral advisor Franco Preparata left Illinois for Brown University in the early 1990s.
"He advocated for me just as if I were truly one of his students," said Amato. "Now that I have a better understanding of how busy Dave must have been, I have a renewed appreciation and amazement at how he was always able to make time for me. He convinced the department to put me forward as its only nomination for a Bell Labs Fellowship which was one of the most prestigious fellowships at the time. I ultimately received the Fellowship and it had a huge impact on my career through the connections and opportunities it provided."
Liu was widely recognized as an engaging speaker and he gave hundreds of talks throughout his career. His trademark opening was to lead off each presentation or lecture with a joke.
Cong fondly recalled one of Liu’s jokes, which he included in his introduction of Liu at the 2011 Kaufman Award ceremony.
A bird lover walks into a pet store and wants to buy a bird, so he asks the owner the cost of three colorful birds. The owner says the yellow bird costs $50,000, which shocks the prospective buyer. “Why is this yellow bird so expensive,” he asks. The owner replies, “This bird can read The New York Times to you.” The buyer then inquires about the cost of the blue bird, which he is told costs $100,000. “How can that be,” he asks the owner. “The blue bird can read Chinese novels to you,” the owner says. Intrigued, the buyer asks how much the red bird costs. “He costs a quarter million dollars,” says the owner. The bird lover is incredulous, so he asks the owner what does this bird do? The owner replies, “To be honest, I really do not know, but the other two birds call him professor.”
Liu is survived by his wife Jane and daughter Kathleen. Memorial contributions can be made to the C.L. Dave Liu Scholarship Fund at the University of Illinois.
A complete summary of Liu’s accomplishments can be found on this memorial page.
In addition to the awards already mentioned, Liu earned the following research and education accolades:
- IEEE and ACM Fellow
- Technical Achievement Award from the IEEE Circuits and Systems Society
- IICM Medal of Honor from the Institute of Information & Computing Machinery in Taiwan
- IEEE Computer Society, Technical Committee on Real-Time Systems Technical Achievement Award
- IEEE Millennium Medal
- IEEE Circuits and Systems Society Golden Jubilee Medal
- Lifetime Achievement Award at the International Conference on VLSI Design
- IEEE Education Medal
- ACM Karl Karlstrom Outstanding Education Award
- IEEE Computer Society Taylor Booth Education
- Honorary doctorates from National Chengchi University and University of Macau
- Distinguished Academic Achievement Alumni Award, Illinois Computer Science
Read more tributes to Professor Liu: