Did everyone watch the Dude movie about Silicon Valley startups? Do you know which startup of the Valley was the most silicone in 1977? It was Silicon Valley Research, also known as SVR and Silvar-Lisco. The startup made programs that automatically placed transistors on the chip site and connected them with tracks. The startup went public and even lived to the 21st century , but could not compete with the new leaders - first Daisy / Mentor / Valid, and then Synopsys and Cadence.The programs that SVR did were called placement and tracing programs, in English Place & Route - P&R. They greatly increased the labor productivity of engineers - before P&R programs, chip mask drawings were glued from color cardboard (Intel 4004), drawn with pencils on paper, or ran the cursor on the text screen and connected elementary blocks represented by stars with pluses and minuses (this is how the chips were designed in IBM / 370-compatible Amdahl computers, advanced relatives of Soviet EU computers).SVR was founded by Stanford professor Bill van Klimpat , whom I knew personally, since he was an angel investor and a member of the board of directors of my own startup. Bill periodically raised me for bad behavior at meetings and procrastination, and also told stories about patent courts, on which he constantly went as an expert witness.Therefore, when in Kazan Innopolis I was asked to organize a project on their hackathon for students on CASE Tools, I remembered Bill and suggested making a minimal routing program on the hackathon. This post is a report on the results of this experimental hackathon. They are also probably worth discussing at the zoom conference in Innopolis on Open Source projects, which will be in a week .
Understanding the physical design algorithms of microchips is a core competency. In all chip design teams in Apple, NVidia, Intel, AMD, Cisco, Juniper, Huawei, Samsung, Tesla, Google, MediaTek, Broadcom - there is a group PD Team (Physical Design Team), which works with tools from Synopsys and Cadence, who do it. Moreover, these tools are complex, they have more than a thousand teams and hundreds of subsystems; they cost each company millions or tens of millions of dollars a year. Without the presence of more PD specialists (both at the user level and at the level of custom PD tools developers), Russia has no chance at all to become significant on the international market of microchips in smartphones, AI accelerators and self-driving cars. Something like some African country where biochemistry is not taught at universities,there is generally no chance of becoming a leader in drugs (any prothesis inhibitors) against coronavirus.Discussions and Objections
We discussed the idea of ​​P&R hackathon on the silicon-russia mailing list , where we were treated with cautious skepticism. In particular, Mikhail Shupletsov, who is engaged in EDA (Electronic Design Automation) algorithms at the VMK Moscow State University, objected to me:Mikhail Shupletsov: “There is doubt that the Hackathon format is suitable for such tasks. A good result on design automation problems can only be obtained if the competition has been going on for a long time (at least 6 months). In the proposed format, in my opinion, it will only be possible to run ready-made tools, but not create a new solution. ”
to which I replied:: « , , capacity ( ) features ( ASIC libraries) . , ! 20 , floorplanning maze router. Tcl/Tk. , EDA. + .»
« — »
The task interested three students of Innopolis. The main intrigue was how to cut down the wording of the task so that it was really possible to complete it quickly, in two weeks of preparation and four hours of hackathon. The original statement of the problem looked like this . It consisted of three parts:- Parsing a text file on a stripped-down subset of the Verilog hardware description language.
- Applications of the ancient Lee wave-tracing algorithm.
- Graphic output of the result.
After discussion with students, we decided to replace the verliogue parsing with a simplified input of cell coordinates from a text file . Then the students assigned responsibilities and below - their three reports about the experiment.In parallel with the students, I decided to write a solution myself, to figure out how long it would take for one person. Students wrote their decision using object-oriented client-server frameworks in Java and web graphics. I just wrote a C program that takes data from an initialized static array and prints the result by printing a picture with asterisks and dots, as in the programs of the 1970s. It took me 4 and a half hours.Code of my (non-student) program.Complete results.
Now we give the floor to students:
Report by Sofia Ermolaeva
The hackathon was held among students of Innopolis University on October 19, 2019.A choice of 11 cases was presented, of which each had to choose 3 and prioritize from the most preferred to the least preferred.According to our preferences and the number of people who selected each case, the organizers formed teams.A week before the hackathon, I and two other students were assigned to the project from MIPS BU.Image 1. Case from MIPS BU on the hackathon website
Our team was the smallest, in comparison, the other teams were 5-7 people. Accordingly, it immediately became clear to us that we are unlikely to master the tasks set for execution within 8 hours. The difficulty was that we were the only ones with a remote customer and even with 10 hours time difference.According to the rules of the hackathon, after the distribution of the teams, it was allowed to hold a series of meetings with the customer to clarify the requirements and familiarize themselves with the technologies if they were not familiar to the teams (which was applicable to our team).We first met with the customer on October 11, 2019. For the meeting, we prepared questions for the Elicitation Interview (even while preparing the questions, we understood that we did not understand at all how to complete the task, but that was even more interesting). The initial list of questions is presented in Image 2. I had to get a lot of wool on the Internet in order to get any level of knowledge on the topic.Image 2. Elicitation interview questions.
During the meeting, we had more detailed questions regarding the solution (see Image 3).Image 3. Issues related to implementation.
As a result of the meeting, we found out we collected the requirements and their priorities so that it was clear how to reduce the scope (see Image 4).Image 4. Requirements and their priorities collected during the first meeting.
The feeling that the three of us didn’t have time for 8 hours did not leave us; we shared our experiences with the customer. It turned out that he did not know about the limit of 8 hours. Therefore, we began to think together about simplifying the task and developing a prototype.Simplifications mainly concerned functional requirement No. 1 (see Figure 4). In our final Requirements Document, the requirements for the prototype are divided by functionality: File reader (see Image 5), Placement (see Image 6), Routing (see Image 7), Graphical representation (see Image 8). According to the rules, the Requirements document needed to be certified with the customer’s signature, but since our customer had a remote confirmation, we decided to make a photo (see Image 9).Image 5. Requirements for File Reader
Image 6. Requirements for Placement
Image 7. Requirements for Routing
Image 8. Requirements for Graphical representation
[Image 9. Confirmation of requirements by the customer.]After collecting the requirements, we began to think through implementation features and technology choices. It is worth noting that our team consisted of: 1 C # developer (Michael), 1 Python developer (Maxim) and 1 Frontent developer (Sofia). For display, we chose React.js since I had enough confidence that using this technology in a short time I could implement the display. For the rest of the components, it was hard to choose a technology because the knowledge varied greatly, we agreed on Java since everyone had at least minimal experience in this language.We shared responsibility as follows:- Display, back and front linking, presentation preparation, team management - Sofia,
- Placement and Routing - Michael
- File reader - Maxim.
During the hackathon, customers had to present cases, but due to the time difference (we had it earlier in the morning and the customer had late night) we showed a video prepared by the customer.After the presentations, we went to code our solution. We sat together but each worked on his part (see Image 10). Of course, before Hackathon, we trained to write the Lee algorithm to understand its operation.[Image 10. Mikhail and I are working on a solution to the problem (Maxim didn’t get into the frame, but he also worked nearby).]I chose Spring to communicate the back and front. To test the solution, we prepared several examples of simple input files (an example of such files is shown in Figure 11).Image 11. Incoming file and its display.
Testing on simple files worked as we expected. Problems arose when we decided to make an example more complicated for a beautiful picture on slides. I came up with an example presented in Image 12. For reasons unknown to us, the algorithm went into an infinite loop. There was an hour until the end of the hackathon. We have already been working hard on the presentation, as it also had to be driven away for a quality presentation. While I was working on the presentation, my teammates found out that the program does not end up in an infinite loop every time, that is, when it starts on the same file, the program sometimes still works. We realized that our solution is not stable. But there was no time to correct. Confirmation of the instability of the algorithm was also the fact that the construction of the circuit for the same file was different (see Figure 13).Image 12. An example invented during the hackathon to demonstrate the operation of the algorithm.
Image 13. Conclusion for the second example (during the hackathon and after the hackathon).
Hackathon we did not win. It is worth noting that the remaining cases were related to quality analysis and product testing, while we implemented the solution from scratch. We were crows on a hackathon. In truth, I am very happy about this, as the experience gained was very useful.[Image 14. Presentation of our solution at the hackathon.][Image 15. Our team with certificates of participation.][Image 16. Our team participates in evaluating other cases.]Post mortemAfter the hackathon, we sent our decision to the customer as a reference to git .On November 4th, I received a letter from the customer stating that he was unable to launch our project. The problem was that we developed on MacOS and Windows, respectively, we also wrote instructions based on how we ran on our platforms.Image 17. The initial instruction for launching the application.
The customer tried to run through the console and received the following error:Image 18. Error No. 1.
It reproduced all the errors and the problem was that to launch the project through the console as a jar, it was necessary to add a manifest file so that maven knew which of the files is the main class. So I added the configuration files and sent the update to the customer.The next letter from the customer came on April 15, 2020. The customer received the following error during the assembly of the project:Image 19. Error No. 2.
I had to deal with the project again. After several hours of trial and error, I still managed to find out the problem. It turned out that javafx.util.Pair even when adding the javafx.util library as a dependency in pom.xml during assembly is not added to the project. After googling, it turned out that all users of this library have such a problem. At first I tried to solve this problem in different ways, but as a result it turned out to be easier to implement the class manually. It turned out that in Python (namely, the Python developer from our team worked on this part), similar classes are used as a standard solution, but in Java there are many other data structures for storing key-value (HashMap etc.). As a result, my code for Pair that helped fix everything was as follows:Image 20. Pair implementation.
After I fixed the error, I decided to write detailed instructions for launching the application through the console. After testing the instructions. We phoned the customer and launched the project. So, after 5 months, the customer was able to see the fruits of our work.Image 21. The final instruction for launching the project.
The initial version of the project is in the github repository.The final version of the project is in my github repository.
Report by Maxim KostinAfter studying all the requirements for the project, we divided the task into 3 main parts.I was responsible for processing the input file and packaging it in a convenient format for further processing. In my opinion, the graph can be considered the most obvious and convenient data structure for this task (we represent the elements as vertices, and the edges of the connection between them).You can implement a graph in different ways, but for this problem I chose the option of implementing a graph on lists (implementing a graph on an adjacency matrix would turn out to be quite discharged and consume more memory, although bypassing the graph on lists in speed in adding edge operations).It was originally planned to process input files written using Verilog syntax, but later on we omitted this aspect and started using a simplified input data format.We also made a number of simplifications (due to the restriction on the hackathon time) on the sizes of the elements (we considered all elements to be the same size), a complete simplification on the physical nature of the elements (signal delays, influence from neighboring cells, energy consumption - to some elements thicker tracks and more).In general, there were no critical errors in the implementation of the graph itself, but in the process of parsing the file a number of errors arose inattentively, for example, for the NOT element, two inputs were initially created (obviously the program crashed).A number of minor errors also occurred (the size of the substrate was incorrectly specified) when combining with Michael's code (Mikhail was involved in placing graph elements on the substrate and tracing), but in general, everything was decided "quickly and painlessly." Michael wrote a very good code, which allowed him to approach the goal significantly quickly.But Michael and I would not have succeeded had it not been in our team Sofia. She was not afraid, and took on the most important part - the visualization of the results (something without which our project would have practically no meaning), and she coped with the task.In general, during the work on the project I learned a lot of new and useful information about how printed circuit boards and SoC are created, as well as what algorithms and people are behind it. I am sure that this skill can be useful to me in the future, because I occasionally dabble in electronics and sometimes collect all kinds of prototypes. Now, I can use our program to make a trace of the tracks, and see how it might look like in reality.
Report by Michael Scheinberg
The reason for my choice of this project was its connection with the example from the book of Eric Evans “Object-Oriented Programming” which I read at that time. Although looking ahead I can say that there was no serious application of my knowledge about DDD, and the experience from the example given in the book at the hackathon, I think that the experience gained at the hackathon was useful and interesting for me.After studying all the requirements for the project, we divided the task into 3 main parts.I was responsible for constructing the scheme, Maxim took over the writing of the parser and Sofia took responsibility for the visualization of the results.Together with the team and the customer, we chose the Floyd algorithm for the optimal placement of wires on the circuit. To store the constructed scheme, a three-dimensional matrix was used where the vertical coordinate was the layer number. Together with the team, a simplification was adopted - each element of the scheme was given the size of 5x5 cells and the space between the elements was 3 cells. Accepted simplifications were associated with the time of the hackathon (it was limited) and the restriction in free time before the start of the hackathon (in the hackathon wound there were a number of large asayments that also needed to be done).In the process of combining the results of my work with the results of Maxim's work, a number of annoying problems arose due to the rush and carelessness associated with the limited time, which, fortunately, were quickly discovered and eliminated.Separately, I want to note the quality of visualization performed by Sofia. Its part worked without errors and provided good material for an informative presentation of the results.In general, during the work on the project, I learned a lot of new and useful information about how the process of constructing microcircuits and the algorithms used in this area that I can apply in the future are arranged.
Appendix A: Objection by Mikhail Shupletsov from Moscow State University (pictured left)The team Mikhail Shupletsov from Moscow State University won the prestigious international competition IC-CAD 2015 , and even the former US Ambassador to Russia Michael McFaul got an emotional response .From the discussion on the silicon-russia mailing list .: , . , :
1. http://iccad-contest.org
2. http://www.ispd.cc/?page=contests
( , ). , :
1. https://arxiv.org/pdf/1810.01078.pdf
2. https://github.com/jinwookjungs/datc_robust_design_flow
I believe that the initiative to hold competitions to develop design automation algorithms is very useful. I myself have experience in managing teams that participated in such competitions. I myself would be interested to participate as an organizer of such competitions.
The only thing that upset a little was that the post about the event in Innopolis appeared after the registration for the event ended. There is also doubt that the Hackathon format is suitable for such tasks. A good result on design automation problems can only be obtained if the competition has been going on for a long time (at least 6 months). In the proposed format, in my opinion, it will only be possible to run ready-made tools, but not create a new solution.
And the second:!
. . , . , ( ) , .
, , .
. . , , EDA - . , EDA , ICCAD ISPD. , ( ). , ICCAD ISPD , , (http://www.mes-conference.ru/) , EDA.
,
Appendix B: Instructions by Sofia Ermolaeva on how to reproduce the resultsRequired:
Maven
Npm
Clone repository
git clone https://github.com/keepYourHairOn/HackathonProject.git
In the repository folder:
cd edap
cd ASICdrawer
npm install
npm start
In the browser open:
localhost:8008
In the new tab of the command line (because node should stay working).
To build new jar:
cd edap
mvn package
Copy input.txt file from {repository folder}/edap/input.txt and paste a file into: edap/target
To run the existing jar:
cd target
java -jar edap-1.0-SNAPSHOT.jar
ReferencesStatement of the problem in an earlier post on Habré.
The document that we drafted with the students.
Preprint of an article by Hackathons as a Part of Software Engineering Education: CASE in Tools Example by Andrey Sadovykh, Maria Naumcheva, Mansur Khazeev, Innopolis University.
PDF articles by Hackathons as a Part of Software Engineering Education: CASE in Tools Example by Andrey Sadovykh, Maria Naumcheva, Mansur Khazeev, Innopolis University.
Photos of the Hackathon.
The sun sets over Silicon Valley, and rises above Innopolis, on which I stop my speech. What do you think?