— as Professor of Computer Science at the University of Rochester, and at his native University of Wisconsin–Madison, he was dean for five years. He is engaged in research in the field of parallel and distributed programming and language design and teaches this to students.
The world knows Michael from the textbook , what about work received the Dijkstra Prize as one of the most famous in the field of distributed computing. You may also know him as the author of the same algorithm .
Together with Doug Lee, he developed those non-blocking algorithms and synchronous queues that Java libraries run on. Implementation in JavaSE 6 allowed 10 times better performance ThreadPoolExecutor.
Contents:
- Early Career, University of Rochester. Charlotte Project, Lynx language;
- IEEE Scalable Coherent Interface, MCS blocking;
- Survival in a constantly changing world;
- Are students getting dumber? Global trends, internationalization;
- Effective work with students;
- How to keep up with the preparation of new courses and books;
- Communication between business and academy;
- Practical implementation of ideas. MCS, MS, CLH, JSR 166, work with Doug Lee and more;
- transactional memory;
- New architectures. A close victory for transactional memory;
- Non-volatile memory, Optane DIMM, ultra-fast devices;
- The next big trend. dual data structures. Hydra.
Interviews are conducted by:
Vitaly Aksenov — currently a post-doc at IST Austria and an employee of the Computer Technologies Department at ITMO University. He is engaged in research in the field of theory and practice of competitive data structures. Prior to joining IST, he received his PhD from Paris Diderot University and ITMO University under Prof. Petr Kuznetsov.
Alexey Fedorov is a producer at JUG Ru Group, a Russian company that organizes conferences for developers. Alexey participated in the preparation of more than 50 conferences, and his resume contains everything from the position of a development engineer at Oracle (JCK, Java Platform Group) to the position of a developer at Odnoklassniki.
Vladimir Sitnikov is an engineer at Netcracker. For ten years he has been working on the performance and scalability of NetCracker OS, software used by telecom operators to automate network and network equipment management processes. Interested in Java and Oracle Database performance issues. Author of over a dozen performance improvements in the official PostgreSQL JDBC driver.
Early Career, University of Rochester. Charlotte project, Lynx language.
Alexey: To begin with, I wanted to tell you that we all love Computer Science, Data Science and algorithms in Russia. Straight to the point of obscenity. We have all read . Therefore, the upcoming conference, the school and this interview itself should be very popular. We received a lot of questions for this interview from students, programmers and members of the community, so we are very grateful to you for this opportunity. Does Computer Science enjoy the same love in the US?
Michael: Our field is so diverse, it has so many directions, and it affects society in such different ways that it's hard for me to give you a definitive answer. But the fact is that thanks to it, over the past 30 years, there have been tremendous changes in business, industry, art and society as a whole.
R'RёS,R ° F "RёR№: Let's start with something remote. In many universities there is something like specialization in one particular direction. For Carnegie Mellon University, these are parallel computing; for MIT, these are cryptography, robots, and multithreading. Is there such a specialization at the University of Rochester?
MichaelA: To be honest, I would say that CMU and MIT specialize in all areas. At our department, the most attention has always been paid to artificial intelligence. Half of our people work in AI or human-computer interaction - this proportion is more than in other departments, and this has always been the case. But when I was at university, I didn't have AI courses and never worked in this field. So my department specializes in a problem that I have nothing to do with. The consolation is that the second most important problem for our department is parallel and multi-threaded programming, that is, my specialization.
R'RёS,R ° F "RёR№: You started doing Computer Science when the field of multi-threaded programming was in its infancy. The list of your publications shows that the first works dealt with a fairly wide range of issues: memory management in multithreaded systems, distributed file systems, operating systems. Why such versatility? Have you tried to find your place in the research community?
Michael: As a student, I participated in at the University of Wisconsin, which developed one of the first distributed operating systems. There I worked with Rafael Finkel () and Marvin Solomon (). My dissertation was devoted to the development of a language for system software for distributed systems - now everyone has already forgotten about it, and thank God. I created the Lynx programming language, which was supposed to make it easier to create servers for a loosely coupled distributed operating system. Since at that time I was mainly involved in operating systems, I assumed that my career would be mainly related to them. But in Rochester, the university was very small, and because of this, different groups there interacted very closely with each other. There weren't a dozen other operating systems people I could talk to, so all the contacts were with people who worked in completely different areas. I really liked it, being a generalist is a big advantage for me. If we talk specifically about multi-threaded data structures and synchronization algorithms, then I started to deal with them quite by accident.
IEEE Scalable Coherent Interface, MCS blocking.
R'RёS,R ° F "RёR№: Can you elaborate a little more on this?
Michael: This is a funny story that I never get tired of telling everyone. It happened at a conference in Boston, it was in the late 80s or early 90s. The conference was attended by John Mellor-Crummy (), a graduate of our faculty. I was familiar with him, but before that we had not conducted joint research. Mary Vernon () from Wisconsin gave a talk on a multiprocessor system they were developing in Wisconsin: . This Multicube had a hardware-level synchronization mechanism called Q on Sync Bit, and later it was renamed Q on Lock Bit, because it could be pronounced like the name of Colby cheese, which was such a pun. If you're interested in multithreading mechanisms, you probably know that Colby eventually became the synchronization mechanism of the IEEE Scalable Coherent Interface standard. It was a locking mechanism that created pointers from one cache to another at the hardware level so that each lock holder knew whose turn it was. When John and I heard about this, we looked at each other and said: why do this at the iron level? Can't the same thing be achieved with compare-and-swap? We took one of the notebooks that lay in the audience and sketched on it while Mary continued her report. Subsequently, we implemented it, experimented, the idea turned out to be successful, and we published an article. Then for me this topic seemed just a fun distraction, after which I planned to return to operating systems. But then another problem arose in the same direction, and eventually synchronization, multithreading and data structures became my main specialty. As you can see, it all happened by chance.
R'RёS,R ° F "RёR№: I have been familiar with MCS blocking for a long time, but until now I did not know that this was your work, and did not understand that this is an acronym for your surnames.
How to survive in a constantly changing world?
Alexey: I have a question on a related topic. 30 or 40 years ago there was more freedom in different specialties. If you want to start a career in multithreading or distributed systems - please, if you want to get into operating systems - no problem. In each area, there were very many open questions and few experts. Now narrow specializations have appeared: there are no just experts in operating systems in general, there are specialists in individual systems. It's the same with multithreading and distributed systems. But the problem is that our lives are not endless, everyone can devote only a few decades to research. How to survive in this new world?
Michael: We are not special in this regard, the same thing happened once in other areas. I was lucky that I started working in Computer Science when this field was in its "adolescent" age. Some foundations had already been laid, but everything was still very immature. Such an opportunity appears infrequently. Electrical engineering has existed for a very long time, physics even longer, mathematics almost from the beginning of time. But this does not mean that no one else makes interesting discoveries in mathematics. There are still many open problems, but at the same time, more needs to be learned. You correctly noted that there are now much more specializations than there used to be, but this only means that we are in the same situation as most other areas of human activity.
Alexey: I'm interested in a more practical aspect of the issue here. I have a background in mathematics and during my studies I often attended conferences and worked on various scientific topics. I found that no one in the audience understood my presentations, and similarly, other people's presentations were only understandable to themselves. In high-level topics, this is not the case, but as soon as you start to delve into something, the audience stops keeping up with you. How do you deal with it?
Michael: Not always successful. I recently prepared a report in which I went too deep into technical details. During the presentation, it became clear that most of the audience did not understand me, so I had to adapt to the situation on the go. The slides could no longer be changed, so it didn't work out too well - so, generally speaking, I try not to use slides. In general, my advice is this - consider your audience. You need to know who you are talking to, what level of knowledge they have, and what they need to hear in order to appreciate your work.
R'RёS,R ° F "RёR№: Could you give a hint about what this lecture was about?
Michael: To be honest, I would prefer not to expand on this topic in order to leave anonymous those people in question. The bottom line is that we often delve too deeply into the intricacies of the problem we are working on, so it becomes difficult for us to explain at the beginning of the report why this problem is interesting and important and how it relates to issues that the listeners already know. According to my observations, this skill is the most difficult for students. And this was the weak side of my recent report. A well-structured report should from the very beginning find contact with the audience, explain to them exactly what the problem is and how it relates to the topics they already know. How technical this introduction will be depends on the audience. If it is completely motley, then the report can be multi-stage. The introduction should be accessible to everyone, and by the end, the part may no longer be able to keep up with you, but people who are relatively familiar with your field will be able to understand everything.
Are students getting dumber? Global trends, internationalization.
Alexey: You have been watching students for several decades. Do students get dumber or smarter from decade to decade or year to year? In Russia, professors constantly complain that students are getting dumber every year, and it's downright unclear what to do about it.
Michael: You can really hear a lot of negativity from us old people. Subconsciously, we have a tendency to expect students to master all the 30 years of experience that we already have. If I have a deeper understanding than in 1985, then why don't students have it? Probably because they are 20 years old, how do you like that? I think the most significant change in recent decades has been in terms of demographics: we now have significantly more international students, with the exception of Canadians. There used to be a lot of Canadians, because we are very close to the border with Canada, and students from there can go home on weekends. But now there are many good universities in Canada, and Canadians prefer to study at home, they have become much less likely to travel to the USA.
Alexey: Do you think this is a local trend or a global one?
Michael: I don't remember exactly who, but someone said that the world is flat. Our area has become much more international. they used to be held exclusively within the United States, then they decided to hold them in other countries every 4 years, and now they are held all over the world. To an even greater extent, these changes affected because it has always been a more international organization than the ACM. And there are program chairs from China, India, Russia, Germany and many other countries, because there is a lot going on everywhere right now.
Alexey: But, probably, there are some negative aspects of such internationalization?
Michael: I would say that all the negative aspects are not related to technology, but to politics. Once upon a time, the main problem was the fact that the US was stealing the smartest and most talented people from countries all over the world. And now the main problem is political games between different countries around visas and immigration.
Alexey: That is, barriers and things like that. It's clear.
Vladimir: Personally, I wonder what approach you take when teaching a new subject to students. After all, there are different options: you can try to inspire them to try something new in the first place, or you can pay more attention to the details of how a certain technology works. What do you prefer?
Effective work with students
Alexey: And how to find a damn balance between the first and second?
Michael: The problem is that classes do not always go the way I would like. I usually give students reading material in advance so that they delve into it, understand it to the best of their ability and formulate questions on those places that they could not understand. Then the class can focus on the most difficult moments and explore them all together. This is how I like to conduct classes the most. But taking into account the workload that is now on the students, it is far from always possible for me to make sure that they prepare in advance. As a result, you have to devote much more time to the general retelling of the material than you would like. Despite this, I try to keep our classes interactive. Otherwise, it's easier to record a video once, which students can then watch at home. The meaning of live classes is in human interaction. In class, I prefer to use chalk and a blackboard rather than slides, except in some cases when a diagram is too complex to be drawn on a blackboard. Thanks to this, I do not have to adhere to a rigid lesson plan. Since there is no set order in which I present the material, it allows me to adapt to the audience depending on the questions I receive. In general, I try to make the classes as interactive as possible, so that the material I present depends on the questions that I am asked.
Vladimir: It's great. In my experience, it is quite difficult to get questions from listeners. Even if you ask in advance to ask any questions, no matter stupid or smart, they are still silent. How do you deal with it?
Michael: You will laugh, but if you stand silently long enough, sooner or later everyone will become uncomfortable, and someone will ask a question. Or you can ask a simple yes or no technical question to determine if people understood what was just said. For example, is there a data race in the above example? Who thinks so? Who thinks not? Who does not understand anything at all, because in total only half of the hands went up?
R'RёS,R ° F "RёR№: And if you answered incorrectly, you are out of the class 🙂
Michael: If you didn't answer anything, you should ask a question. I need to understand what exactly the student needs to know in order to answer the question I just asked. I need them to help me help them. I am ready to adapt to them so that they understand the problem. But if I don't know what's going on in their head, I can't do it. And if you don't let the students rest for long enough, then sometimes they end up asking the right questions, that is, those thanks to which I see what exactly is going on in the minds of the students.
Alexey: Do these questions sometimes lead to ideas that you yourself have not thought of before? Are they unexpected? Do they allow you to look at some problem in a new light?
Michael: There are questions that open up a new way of presenting material. There are often questions that lead to interesting problems that I didn't plan to talk about. Students often tell me that I have a tendency to get off topic when this happens. And, according to them, very often this is the most interesting part of the lesson. Quite rarely, just a few times, students asked questions that prompted a new direction in the study and grew into an article. This happens much more often in conversations with students, and not during classes, but occasionally it happened during classes.
Alexey: That is, the students asked you questions, on the basis of which it was then possible to publish an article?
Michael: Yes.
R'RёS,R ° F "RёR№: How often do you have such conversations with students? When do they want to learn more than what was covered during the session?
Michael: With my graduate students - all the time. I have about 5 or 6 of them, and we discuss something with them all the time. And conversations of this kind with students who simply attend my classes are not very common. Although I would like it to happen more often. I suspect that they are simply afraid to come to the faculty during reception hours. Every semester, some students manage to overcome this psychological barrier, and it is always very interesting to talk with them after class. True, if all students were as brave, I simply would not have enough time. So maybe everything is working as it should.
R'RёS,R ° F "RёR№: How do you manage to find time to communicate with students? As far as I know, teachers in the USA have a lot of work - applications for grants and the like.
Michael: To be honest, working with students is the aspect of my work that I like the most. So I have enough motivation for this. Most of the time I spend in my office is spent in all sorts of meetings. It's summer now, so the schedule is less busy, but during the school year, every day from 9 to 17 I have everything packed. Research work, reviews, grants - for all this there are only evenings and weekends.
How to keep up with the preparation of new courses and books.
Alexey: Do you continue to teach any of the courses that you have been taking for a long time now? Something like an introduction to Computer Science.
Michael: The first thing that comes to mind here is a course in programming languages.
Alexey: How different is today's version of this course from the one that was 10, 20, 30 years ago? Perhaps what is more interesting here is not the details of a particular course, but the general trend.
Michael: My course in programming languages was somewhat unusual at the time I created it. I started reading it in the late 1980s, replacing my colleague, Doug Baldwin (). The topic of the course was only tangentially related to my specialization, but when he left, I was the best candidate to teach this course. I didn't like any of the textbooks that existed then, so I ended up writing the textbook for this course myself. (Editor's note: This is a book) It is now used by more than 200 universities around the world. My approach is unusual in that it deliberately mixes language design and implementation issues, and places great emphasis on the interplay between these aspects in every possible area. The basic approach has remained unchanged, as have many basic concepts: abstractions, namespaces, modularity, types. But the set of languages with which these concepts are demonstrated has changed entirely. When the course was first created, there were many examples in Pascal, and today many of my students have not even heard of such a language. But they know Swift, Go, Rust, so I have to talk about the languages that are in use today. Also, students are now well versed in scripting languages, and when I started teaching this course, it was all about compiled languages. Now we need a lot of stuff about Python, Ruby and even Perl, because that's what we write code in these days, there are a lot of interesting things going on in these languages, including in the field of language design.
R'RёS,R ° F "RёR№A: Then my next question will be related to the previous one. How to keep up in this area? I suspect that updating such a course requires a lot of work - you need to understand new languages, understand the main ideas. How do you do it?
Michael: I can't boast that I always do it 100%. But most of the time, I just do what everyone else does — read the internet. If I want to understand Rust, I type it into Google, go to the Mozilla page and read the manual posted there. It's part of what happens in commercial development. If we talk about science, then here you need to follow the reports at the main conferences.
Relationship between business and academy
R'RёS,R ° F "RёR№: Let's talk about the relationship between business and research. In the list of your works, I found several articles on cache coherence. I understand the cache consistency algorithms were unstable at the time they were published? Or not common enough. How common were your ideas in practice?
MichaelA: I'm not exactly sure which publications you're talking about. I have done quite a lot of work with my students Bill Bolosky () and Leonidas Kontotanassis () in the early 1990s on the memory management of Neumann machines. At that time, the business did not yet have an understanding of how to correctly make a multiprocessor system: is it worth creating support for access to remote memory at the hardware level, is it worth making memory distributed, is it possible to load the cache from remote memory, or is it necessary to move pages in the operating room? system. Bill and Leonidas have both worked in this area and explored approaches without remote cache loading. It wasn't directly related to cache consistency, but it was still work on NUMA memory management, and from that grew modern approaches to page placement in modern operating systems. All in all, Bill and Leonidas did important work, although not the most influential in this area - at the time, many other people were working on the same thing. More recently, I have dealt with the topic of cache consistency in the context of hardware transactional memory. The group I worked with on this problem ended up with several patents. There are some pretty interesting ideas behind them, but I don't think they will end up being implemented in practice. Anyway, it's hard for me to judge their profitability.
Alexey: In this regard, a more personal question: how important is it for you that your ideas are put into practice? Or don't you think about it?
Michael: I love asking this question in interviews with other people, applicants or candidates who want to work on the faculty. I don't think there is a correct answer to this question. People who do cool things can have all sorts of motivations. Problems attract me because they seem interesting to me personally, and not because of their practical benefits. But on the other hand, when some interesting thing still finds a use for itself, I really like it. So it's not easy here. But at the beginning of the work, it’s still not the idea of \uXNUMXb\uXNUMXbend use in the world that drives me, but the harmony of the idea and the desire to explore it and see what comes of it. If in the end it gives a practical return - great.
Alexey: Thanks to your education and experience, you are better than many able to appreciate the value of other people's ideas. You can compare them and determine what works best with what. I'm sure you have an opinion about things being used in practice by large manufacturers like Intel. To what extent, in your opinion, is the course followed by these companies correct?
Michael: The practice always revolves around what can be commercially successful, that is, create profit, and you'd better ask someone else about this. My work mostly ends with publications, and in the field of operating systems, they are measured by performance indicators: speed, power consumption, code size. But it always seemed to me that these empirical results are added to articles only so that they can be published, and people's real motives for working are aesthetic. Researchers evaluate solutions from an artistic point of view, they care about how elegant the ideas are, and they try to create something better than existing approaches. Researchers are driven by personal, subjective, aesthetic motives. But you can't write about this in the article itself; for the program committee, these things are not arguments. Fortunately, elegant solutions are also often fast and cheap. A dozen of my colleagues and I discussed this topic about 15 years ago and ended up writing an article about it. I think you can still find it now, it's called or something like that, it has more than a dozen authors. This is the only article in which I am the author along with , so if you do a search for her name in my list of posts, you'll find what you're looking for. It talks about evaluating systems research and how important elegance is.
Alexey: That is, there is a difference between the standard of what is considered a good result in science and in business. Science evaluates performance, power consumption, TDP, ease of implementation, and more. Do you have the opportunity to conduct this kind of research at the university? Do you have a lab with different machines and different architectures where you can run experiments?
Michael: Yes, our department has a lot of different interesting machines. Most often they are small, we have a small cluster and many multiprocessor systems with different accelerators. In addition, the campus has a huge computing center that serves scientists from several dozen different disciplines. It has about a thousand nodes and twenty thousand cores, all on Linux. If the need arises, you can always buy some AWS. So with iron, we have no significant restrictions.
AlexeyQ: How was it thirty years ago? Were there problems then?
Michael: Then it was a little different. In the mid to late 1980s, it was believed that science lacked computing resources. To remedy this situation, the National Science Foundation ) created a program of coordinated experimental research (Coordinated Experimental Research, CER). The goal of this program was to provide a computing infrastructure for Computer Science departments, and it has achieved significant changes. With the money she provided, we at the University of Rochester bought a 1984-knot BBN Butterfly in 128, this was a year before I appeared there. At the time, it was the world's largest shared-memory multiprocessor system. She had 128 processors, each on a separate motherboard, she occupied four racks. Each processor had a megabyte of memory, 128 megabytes of RAM at that time was an unimaginable amount. On this machine, we implemented MCS locking for the first time.
Alexey: That is, if I understand you correctly, then at the moment the problem with the iron is solved?
MichaelA: Generally speaking, yes. There are a few caveats: first, if you're doing computer architecture at the chip level, it's hard to do in academia, because there are far better tools in business for that. If you need anything less than 10 nanometers, then it will have to be ordered from someone on the side. In this area, it is much easier to be a researcher at Intel. If you're working on optical communications on chips or solid-state memory, you'll find technologies in business that aren't in science yet, so you have to forge alliances. For example, Steven Swanson () created for new memory technologies. This form does not always work, but in some cases it can be quite successful. In addition, the development of the most powerful computing systems is more difficult in science. The largest supercomputing projects now in the US, Japan, and China are all in business.
Practical implementation of ideas. MCS, MS, CLH, JSR 166, work with Doug Lee and more.
R'RёS,R ° F "RёR№: You have already talked about how you started working on synchronization algorithms. You have two very famous articles about и , which in a certain sense were implemented in Java. (Editor's note: all publications can be viewed ). There, this blocking was implemented with some changes and it turned out , and the queue was implemented as intended. But many years passed between the publication of your articles and their practical application.
AlexeyA: It seems like about 10 years in the case of the queue.
Michael: Before these features appeared in the Java standard library?
R'RёS,R ° F "RёR№: Yes. What did you do to make this happen? Or did they do nothing?
Michael: I can tell you how the MS queue got into Java 5. A few years before it was introduced, I worked with Mark Moyers' group at Sun Microsystems in their lab near Boston. He organized a seminar for his acquaintances who dealt with interesting problems in multithreading, because he wanted to find topics that could be sold to their company. That's where I first met Doug Lea. Doug, myself, and about 25 other people from Sun were talking together about Doug's presentation about , which later became java.util.concurrent. Along the way, Doug said that he would like to use the MS queue, but for this he needed a counter for the number of elements in the queue for the interface. That is, this should have been done by a separate method, atomic, accurate and fast. I suggested to just add the serial numbers to the nodes, take the number of the first node and the last one and subtract one from the other. Doug scratched his head, said “why not”, and in the end he did. We discussed with him the implementation of this approach in the library, but Doug did most of the work himself. As a result, he managed to establish excellent support for multithreading in Java.
Alexey: That is, if I understand correctly, the .size() method was supposed to be part of the standard queue interface, and it should have an algorithmic complexity of O (1)?
Michael: Yes, and besides this, a separate counter is needed.
Alexey: Because if you call the .size() method in Java, the result is expected to be available immediately, and not depending on the actual size of the collection. I understand, thanks.
Michael: A few years later, I worked on dual data structures with my student Bill Scherer - in fact, my . Doug approached us and said that they would be useful to him in the Java Executor Framework. Together with Bill, they created two implementations, the so-called fair and unfair queues (fair and unfair queues). I advised them on this project, although I did not participate in writing the actual code. As a result, the speed of executors has increased significantly.
Vladimir: Have you encountered incorrect implementations of your algorithms or requests to add new features? In general, practice should coincide with theory, but quite often they differ. Suppose you wrote an algorithm, and on paper it works, but the people who are involved in the implementation began to ask you for more features or some kind of tweak to the algorithm. Have you had such situations?
Michael: The only example in which I was approached and asked "how to implement" is Doug's question, which I already talked about. But there have been a few cases where interesting changes have been made according to practical needs. For example, the K42 team at IBM converted the MCS lock and made a standard interface that eliminated the need to pass the queue node back and forth to the acquire and release routines. Thanks to this standard interface, an idea that was beautiful in theory began to work in practice. It is surprising that they never published an article about this, and although they received a patent, they later abandoned it. The idea was great, and I try to talk about it whenever possible.
There have been other cases where people have made improvements to the algorithms I've published. For example, the MS queue has a two-stage setup mechanism, which meant that there were two CASs on the queue's critical path. On older machines, CAS were quite expensive. Lately, Intel and other manufacturers have been optimizing them quite well, but once they were instructions with 30 cycles, so it was undesirable to have more than one on the critical path. As a result, a great queue was developed that was similar to the MS queue, but which had only one atomic operation on the critical path. This was achieved due to the fact that during a certain period of time, the operation could take O (n) time, not O (1). It was unlikely, but possible. This happened due to the fact that at certain moments the algorithm bypassed the queue from the beginning to the current position in this queue. In general, the algorithm turned out to be very successful. As far as I know, it's not very widely used, partly because atomic operations require significantly less resources than they used to. But the idea was great. I also really like the work of Dave Dice at Oracle. Everything he does is very practical and he uses iron very skillfully. He had a hand in a large part of NUMA-aware synchronization algorithms and multi-threaded data structures.
Vladimir: When you write algorithms or teach students, the result of the work is not immediately visible. The community needs some time to read, say, a new article. The new algorithm does not immediately find its application.
Michael: It is far from immediately clear whether the article will be significant or not. I think it would be interesting to do a study of papers that won awards at conferences. That is, to look at the articles that people in the program committees at one time considered the best. We need to try to calculate by the number of links and by the impact on the business, how influential these articles really turned out to be in 10, 20, 25 years. I doubt there would be a strong correlation between the two parameters. It will not be zero, but, most likely, it will be much weaker than we would like. Many ideas go unclaimed for a long time before they become widespread. For example, take transactional memory. More than 10 years have passed since the publication of the original article until the time when people actually began to create cars with it. And before the advent of this memory in commercial products - and all 20. For a very long time no one paid attention to the article, and then the number of links to it sharply increased. It would be difficult to predict this in advance. On the other hand, sometimes ideas find implementation right away. A few years ago, I wrote a paper with Joe Izraelevich for DISC proposing a new formal definition of correctness for persistent data structures that could be used after the host computer crashed. I liked the article from the very beginning, but it turned out to be much more popular than I expected. It was used by several different groups and eventually became the standard definition of persistent structures. Which, of course, is nice.
Vladimir: Are there any methods that you use to evaluate? Do you even try to evaluate your articles, your students? In terms of whether the person you taught is going in the right direction.
Michael: Like everyone else, I pay more attention to what I'm doing at the moment. Again, like everyone else, I occasionally check Google Scholar to see if my past papers are being cited, but that's more out of curiosity. Basically, I'm absorbed in what my students are doing now. As for the evaluation of the current work, then partly aesthetic considerations work here, what is elegant and what is not. And at the everyday level, open questions play a big role. For example, a student comes to me with a graph of some results, and we are trying to understand where some strange behavior of the graph came from. In general, in our work we are constantly trying to understand things that we do not yet understand.
transactional memory
R'RёS,R ° F "RёR№: Can we talk a little about transactional memory?
Michael: I think it's worth saying at least a little, because I put a lot of effort into it. This is a topic on which I have more publications than any other. But at the same time, oddly enough, I was very skeptical about transactional memory all the time. In my opinion, (M. Herlihy, JEB Moss) was published ahead of its time. In the early 1990s, they suggested that transactional memory could help talented programmers working on multithreaded data structures so that these structures could then be used as libraries by ordinary programmers. That is to say, it would be of help to the Doug Lees working on their JSR 166. But transactional memory was not meant to make multi-threaded programming easy. But this is how they began to perceive it in the early 2000s, when it became widespread. It was advertised as a way to solve the problem of parallel programming. This approach has always seemed hopeless to me. Transactional memory could only make it easier to write parallel data structures. This is what I think she achieved.
On the complexity of writing multi-threaded code
Alexey: Very interesting. There seems to be a certain barrier between ordinary programmers and those who can write multi-threaded code. Last year, I talked several times with people who were involved in the implementation of some algorithmic framework. For example, with Martin Thomson, as well as with programmers working on multithreaded libraries. (Editor's note: Martin Thompson is a very famous developer, he wrote и . And he also has at our conference Joker 2015, video recording . He is this conference, also available). According to them, the main difficulty is that the algorithms are both fast and easy to use. That is, they are just trying to overcome this barrier and attract as many people as possible to this area. What do you think of it?
Michael: This is the main problem of multithreading: how to achieve high performance without increasing the complexity of the system.
AlexeyA: Because when they try to avoid complexity, the algorithm becomes less generic.
Michael: The main thing here is properly designed abstractions. It seems to me that this is generally the main thing for computer systems as a field. Butler Lampson likes to use the term, and he calls us "abstraction dealers." Simple technologies do not exist today. In the processors that we use, there are 10 billion transistors each - there can be no question of simplicity here. At the same time, ISA is much simpler than a processor, since we have worked for a very long time to provide high performance for it and a relatively simple interface. But it's not all smooth sailing for her either. The same problem with accelerators that are now appearing on the market. Questions arise - how to make the right interface for the GPU, an encryption mechanism, compression, a transcoding mechanism, a linear algebra engine, or even a more flexible FPGA. How do you make an interface that makes the tool easy to use and hides complexity? It will not get rid of it, namely, it will hide it from a simple programmer.
Alexey: I understand that we still have a barrier in understanding abstractions. Let's take a memory model, at our stage of development of science and technology, this is one of the main abstractions. Thanks to it, all programmers are divided into two groups: the majority are those who do not understand it, and the smaller one is those who understand, or think they understand.
Michael: That's a good question - do any of us really understand the memory model.
R'RёS,R ° F "RёR№: Especially in C++.
Michael: Talk to Hans Boehm sometime. This is one of the smartest people I know, a leading expert on memory models. He will immediately tell you that he does not understand a lot there. But if we return to the issue of abstractions, then, in my opinion, the most important thought in the field of memory models over the past 30 years was expressed by . (Editor's note: a complete list of publications is available ).
Alexey: My question is: does this barrier come from the very nature of the concept?
Michael: No. Sarita came to the conclusion that with the right approach, you can successfully hide all the complexity, get high performance and give the programmer a simple API. And if you follow this API, you can achieve consistent consistency. I believe this is the correct model. Write code without data races and get consistent consistency. Of course, in order to reduce the likelihood of racing, you need special tools, but that's another matter.
Vladimir: Have there been cases in your career when a problem that seemed to be solved suddenly turned into a whole disaster, or it turned out that this problem was unsolvable? For example, in theory, one can factorize any number, or determine whether any number is prime. But in practice, this can be difficult to do, with the current hardware it is difficult to factorize numbers. Has something similar happened to you?
Michael: I don't remember anything like that right off the bat. It happened when it seemed to me that there was nothing left to do in some area, and then something new and interesting happened there. For example, I thought that the area of unlimited queues was already mature. After several improvements to the MNS queue, nothing much happened anymore. And then Morrison (Adam Morrison) and Afek (Yehuda Afek) invented . It became clear that an unlimited multi-threaded queue was possible, which most of the time had only a fetch-and-increment instruction on the critical path. And this made it possible to achieve an order of magnitude better performance. Not that we don't know that fetch-and-increment is a very useful thing. Eric Freudenthal wrote about this in his work on Ultracomputer with Allan Gottlieb in the late 1980s, but it was about limited queues. Morrison and Afek were able to use fetch-and-increment on an unbounded queue.
New architectures. Is transactional memory close to winning?
Vladimir: Do you keep track of new architectural solutions that could be useful for algorithms?
Michael: Of course, there are many things that I would like to see implemented.
Vladimir: And what, for example?
Michael: First of all, a few simple extensions to our hardware-level transactional memory in Intel and IBM processors. In particular, I would like the non-transactional load and store that just happened to be immediately available within transactions. They immediately lead to cycles in the happens-before sequence, so they can be tricky. But if you maintain layers of abstraction, there are a lot of very interesting things that can be done outside of a transaction while it is in progress. I don't know how difficult it would be to implement, but it would be very helpful.
Another useful thing is loading the cache from remote memory. I think sooner or later it will be done. This technology will allow creating systems with disaggregated memory. It will be possible to keep, say, 100 terabytes of non-volatile memory in a rack, and the operating system itself will dynamically decide which sections of this memory should correspond to the physical address space of processors. This would be extremely useful for cloud computing, as it would allow large amounts of memory to be provided to those tasks that need it. I think someone will do it.
R'RёS,R ° F "RёR№: To finish talking about transactional memory, I have one more question on this topic. Will transactional memory eventually supplant standard multithreaded data structures?
Michael: No. Transactions are a speculative mechanism. At the programming level, these are atomic locks, and inside they are speculations. Such forecasting works if most of the guesses are correct. Therefore, transactional memory works well when threads hardly interact with each other, and you just need to make sure that there are no interactions. But if a message starts between threads, transactions are of little use. Let me explain, we are talking about the case when transactions are wrapped around the entire atomic operation. They can still be successfully used as building blocks for multithreaded data structures. For example, if you need a three-word CAS, and you need to multi-thread three small things in the middle of a truly multi-threaded algorithm that works with twenty threads at the same time. In general, transactions can be useful, but they won't get rid of the need to properly design multithreaded data structures.
Non-volatile memory, Optane DIMM, ultra-fast devices.
R'RёS,R ° F "RёR№: The last thing I would like to talk about is the topic of your current research: non-volatile memory. What can be expected in this area in the near future? Perhaps you know of any efficient implementations that already exist?
Michael: I'm not a hardware expert, I only know what I read in the news and what my colleagues tell me. Everyone has already heard that Intel is selling , which have about 3 times more read latency and 10 times more write latency than dynamic RAM. They will soon be available in very large volume versions. It's funny to think that it will be possible to have a laptop with several terabytes of byte-addressable RAM. It is likely that in 10 years we will decide to use this new technology, since we use DRAM - just increase the volume. But thanks to energy independence, completely new opportunities open up for us. We can fundamentally change the storage stack so that there is no separation between byte-addressed working memory and block-structured persistent memory. Thus, we will not need to serialize into block-structured files everything that needs to be transferred from one program launch to another. Many important principles can be deduced from this that affect operating systems, runtime environments, and distributed data stores. It is very interesting to work in this area. Personally, it is difficult for me to predict what this will all result in, but the problems here are extremely entertaining. There will probably be revolutionary changes here, and they follow very naturally from the work on multithreading, since crash recovery is a "threaded" process next to the normal operation of the system.
The second main topic I'm currently working on is managing ultra-fast devices and securely accessing devices from userspace with system policy control. In recent years, there has been a trend to move access to the device to the user space. This is done due to the fact that over the network interface, which needs a new packet every 5 microseconds, the kernel TCP-IP stack cannot function, it simply will not keep up. Therefore, manufacturers provide direct access to devices. But this means that the operating system loses control over the process, and it cannot provide correct access to the device for competing applications. Our research team believes that this shortcoming can be avoided. USENIX ATC will have our article on this this month. It has to do with persistence work, since long-lived byte-addressable persistent memory is essentially a super-fast I/O device that needs to be accessed in userspace. These studies enable new approaches to microkernels, exokernels, and other traditional attempts to securely port functionality from the OS kernel to the userspace.
Vladimir: Byte-addressable memory is great, but there is a physical limitation - the speed of light. And this means that there will inevitably be a delay when interacting with the device.
Michael: Quite right.
Vladimir: Will there be enough capacity to cope with new loads?
Michael: That's a great question, but it's going to be hard for me to answer. The idea of in-memory processing has been around for quite some time now, and it's very interesting, but also very complex. I have not worked in this area, but it would be great if some discoveries were made there. I'm afraid I have nothing more to add.
Vladimir: There is another problem. New, significantly larger amounts of RAM will not fit into the CPU. Therefore, due to physical limitations, this RAM must be isolated.
Michael: It all depends on the number of defects in the production of integrated circuits. If it were possible to create completely defect-free semiconductor wafers, then it would be possible to make a microcircuit out of it entirely. But now we can't make chips bigger than postage stamps.
Vladimir: But we are still talking about huge sizes, about centimeters. This inevitably has an impact on latency.
Michael: Yes. Nothing can be done about the speed of light.
Vladimir: Unfortunately.
The next big trend. dual data structures. Hydra.
R'RёS,R ° F "RёR№: As far as I understand, you catch new trends very quickly. You were one of the first to get involved in transactional memory, and one of the first in non-volatile memory. What do you think the next big trend will be? Or maybe it's a secret?
Michael: To be honest, I don't know. Hopefully I'll be able to spot when something new comes up. I have not had the good fortune to invent any new field alone, but on several occasions I have been fortunate enough to be able to start working fairly early in new fields created by others. I hope I will be able to do this in the future as well.
Alexey: The last question in this interview will be about your performance at Hydra and your class at school. If I understand correctly, the report at the school will be about algorithms without blocking, and at the conference about double data structures. Could you say a few words about these reports?
Michael: In part, we have already touched on these topics with you in this interview. It will be about the work that I did with my student Bill Scherer. He wrote a dissertation based on it, and Doug Lee also contributed to it, and eventually it became part of the multi-threaded synchronous queues in the Java library. Let's assume that the data structure is read and written without blocking, that is, each operation has a limited number of instructions on the critical path. If you try to remove data from an empty container, or try to remove certain data that is not in this container, then it is immediately reported that this cannot be done. But this behavior may be unacceptable if this data is very necessary for the thread. Then the first thing that comes to mind is to create a loop that will constantly ask if the necessary data has appeared. But then there is interference for everyone else. In addition, with this approach, you can wait 10 minutes, and then some other thread will come in, and it will accidentally receive the necessary data first. Dual data structures still don't have locks, but they do allow us to properly wait for threads. The term "double" means that the structure contains either data or requests for data, let's call them anti-data. So if you try to retrieve something from an empty container, the request will be put into the container instead. Now the thread can wait for a request and not bother anyone else. In addition, the data structure prioritizes requests so that when received, it passes them on to the right person. This results in a mechanism without blocking, which at the same time has a formal specification and good performance in practice.
Alexey: What are your expectations for this data structure? Will it improve performance in all typical cases, or is it better suited for certain situations?
Michael: It is useful if, firstly, you need a container without blocking, and, secondly, you need to wait in a situation where you need to retrieve data from the container that is not in it. As far as I know, our structure provides optimal behavior when these two conditions are met. Therefore, in these cases, I recommend using it. The main advantage of lockless data structures is that they avoid performance issues. And waiting is very important in many algorithms if data is being transferred from one thread to another.
R'RёS,R ° F "RёR№: Let me clarify: will you talk about the same thing both at school and at the conference?
Michael: At school in general about multi-threaded data structures, with a summary of the basic principles at the beginning of the lesson. I mean that the audience knows what threads are and is familiar with locks. Based on this basic knowledge, I will talk about data structures without locks. I will give an overview of the most important issues in this area, touching on topics like memory management. I do not think that there will be anything more complicated than the MS queue.
Alexey: Do you plan to talk about double data structures at the end of your class at school?
Michael: I will mention them, but I will not devote much time to them. The report on Hydra will be devoted to them. It will talk about the project that ended up in Java, as well as working with Joe Israelevich to create a dual version of the LCRQ queue, and to create a near-universal design for dual data structures.
Alexey: That is, a lecture at school can be recommended for beginners, and a lecture on double data structures on Hydra - for people who already have some experience?
Michael: Correct me if I'm wrong, but the Hydra audience will be quite diverse, including many Java experts, and generally people who are not specifically involved in multi-threaded programming.
R'RёS,R ° F "RёR№: Yes, it is true.
AlexeyA: At least we hope so.
Michael: In this case, I will face the problem with which we started this interview: how to make a report at the same time rich in technical details and accessible to all listeners.
R'RёS,R ° F "RёR№: Will you conduct a report the way you lecture? That is, to talk with the audience and adapt to the situation?
Michael: I'm afraid it won't work, because the report will be with slides. Slides are important when listeners initially speak different languages. Many will find it difficult to understand me in English, especially if I speak too fast. I chose these topics because asked me to talk about lock-free data structures at the SPTDC School; and then I needed a talk for a Java user group conference, and I wanted to pick something that would be of interest to Java programmers specifically. It was easiest to talk about those things in the Java library that I somehow had a hand in.
Alexey: We assume that the Hydra audience already knows something about lock-free programming and may have some experience in this area. But this is only an assumption, the situation will become clearer already at the conference itself. Anyway, thanks for taking the time for us. I'm sure the interview will be very interesting to our readers. Thanks a lot!
R'RёS,R ° F "RёR№: Thank.
Michael: I will be glad to meet you in St. Petersburg.
Alexey: We too, we have a beautiful city. Have you ever been here?
Michael: No, I have never been to Russia at all. But St. Petersburg has always been on the list of places where I have not yet been, but where I really want to go, so I was very happy with the invitation.
Alexey: By the way, we will have a program of excursions for speakers. Thank you very much for the interview and have a great day!
It will be possible to continue communication with Michael at the Hydra 2019 conference, which will be held on July 11-12, 2019 in St. Petersburg. He will come with a report . Tickets can be purchased .
Source: habr.com