Pangenomic graph query acceleration: lab notebook

[sampsyo]

The pangenomics project described in calyxir/calyx#884 is now underway! @dc854 and @Evan-Williams-02 have gotten started with understanding our first pangenomic graph query algorithm from odgi (node depth), and we have a fresh repository for this work.

We're setting up this discussion thread as a "lab notebook" to keep a log of the project's process. There are two purposes: to help save state so we can remember what we're working on, and as a casual way to keep other people interested in the Calyx project up to date about how things are going. The idea is that, each week, @dc854 & @Evan-Williams-02 will post a brief message with these ingredients:

1. What have you been up to this week?
2. What questions, if any, do you have based on that work?
3. What are your plans for next week?

Those updates may lead to additional discussion on the thread.

[evanmwilliams]

Tuesday March 29:

1. This week I've been attempting to get used to gfaPy a bit more, since some of the functions are confusing. I then started playing around with an implementation of the graph algorithm in Python, but it doesn't appear to pass any of my tests at the moment so I need to spend some more time on it. Finally, I gave the dahlia matrix problem another go just to familiarize myself a bit more with the language.
2. How are some of the features in the C++ code we see implemented in Python? Or do we not care? Also, is a meeting with the odgi creators still on the table?
3. Finish the depth algorithm

[sampsyo]

Great! Any particular functions that were confusing? (Links to the docs could help!)

And yep, still working on finding a time with Erik to ask detailed questions about the code.

[dc854]

1. I tried to write a depth implementation based on the C++ code but got a little lost in what the code was doing, so instead I'm trying to write an implementation of the depth algorithm from the high level explanation. However, I don't think I'm actually traversing the graph, so it isn't really working. There's a __traverse_component in the gfapy package that I am trying to understand at the moment.
2. I saw that that there was a python module in the odgi code using pybind11 and was wondering if there was something relevant or something we could use from it?
3. Hopefully, get the graph traversal working and get the depth function working.

[sampsyo]

About the Python bindings to odgi: yeah, those look like they're fairly complete. But TBH I'm not 100% clear what we would use them for. At least at this juncture, the idea behind reimplementing an algorithm that already exits is to prove that we understand it, and we can begin to do differential testing to compare against the odgi implementation. So we wouldn't want to reuse too much of odgi. Maybe one use case could be loading up the og file format and dumping out a representation that our accelerator can use.

[evanmwilliams]

Tuesday April 12

1. Due to prelims, I unfortunately haven't made a lot of progress. My schedule blows wide open after today and until finals, so I expect to be able to get a lot done. I did look at the code David pushed and I have some ideas for how to start testing
2. Any preliminary results on whether David's implementation matches the odgi output?
3. Start testing and playing with a dahlia implementation!

[dc854]

1. I wrote a preliminary version of the depth algorithm that appears to accurately calculate the depths of each path, but the mean depth is still not accurate, so I started exploring that (not much progress though). I was also thinking about how we can create the testing framework since it seems simple enough to integrate into the code I already have.
2. Not at the moment.
3. Hopefully, figure out how mean depth works.

[dc854]

Tuesday April 19

1. I worked on the second implementation of the depth algorithm where the .gfa file is transformed into a json format that can run on the new implementation of the depth algorithm. Then, trying to fix gfapy to work remove the dependencies on links having the same amount of overlap as specified in the path.
2. No questions :)
3. Hardware implementation?

[sampsyo]

Great! As always, can you please push your code early and often, even if it's incomplete? In particular, it would be interesting to see what the data format looks like.

[evanmwilliams]

Tuesday April 19

1. Finished up diff testing implementation. Need to work on making a new output format - I've been playing around with JSON a bit and have a good handle of how to do it.
2. I seem to just be using terminal to do a lot of this right now. Is there a better way to make this testing framework into more of a "unit test"? (pyTest?)
3. Finish up with the new file format and figure out how to integrate it with what David's been up to

[sampsyo]

Awesome; glad that the initial version of the test is working! Can you push what you have so we can try it out ourselves?

Is it possible to run the comparison automatically on multiple .dfa input files?

I'm not entirely sure what you mean by using the terminal... it seems inevitable that this test harness will be a command-line affair. The main goal is to have (and document in the README!) a single command that runs all the tests we have and summarizes their results. For bonus points, you can make a make test target in the Makefile so people don't even have to remember what command to run.

Something like PyTest is useful for unit tests, but these aren't really unit tests---they're integration tests, i.e., they test the whole end-to-end implementation. So I don't think it would be too useful in this case.

[rachitnigam]

We use runt to write tests for the Calyx compiler which allows you to define a single command that can be run over multiple input files. Runt handles the job of running the tests, generating "golden outputs" which are files that document the behavior of the test by capturing its STDOUT and STDERR, and reporting test status.

[dc854]

Tuesday April 26

1. I updated some of the code for the flat file implementation for the depth algorithm. Also installed Dahlia and have been trying to figure out how to write some of the depth code with it.
2. Just general Dahlia questions that I might ask Evan first as I am running into a few errors while compiling the code.
3. Refactor some of the code in the second depth implementation and get the Dahlia implementation working as well.

[sampsyo]

OK, great! Hopefully we can dive deep into some Dahlia questions today. 😃

[evanmwilliams]

Tuesday April 26

1. Finished up the diff testing automation (the bash script is fancier so I hope it's helpful)! Need to push a few minor fixes from what I fixed up on Friday.
2. No questions at the moment!
3. I'll be moving forward to help David with the Dahlia implementation

[sampsyo]

Sounds excellent! Maybe it is time now to merge #3 and make sure it also tests @dc854's new flat-file-based implementation?

[evanmwilliams]

Tuesday May 3

1. Drafted presentation slides; started re-familiarizing myself with Dahlia
2. No questions at the moment
3. Didn't get a chance to meet up with David this past week - will prioritize it this coming week :)

[dc854]

Tuesday May 3

1. Fixed up the Dahlia code to work in compiling to C++, but when compiled to Calyx, it ran for a long time, so I spent some time trying to debug it.
2. None at the moment.
3. I'll sync up with Evan about the presentation and get some help with the debugging and hopefully get it working this week.

[sampsyo]

OK! Did you get a chance to try the various approaches we talked about w/r/t debugging last week (the interpreter, test case reduction)?

[susan-garry]

Monday, June 13

1. Since I started working, I have set up odgi and followed the tutorial for computing node depth. I'm not sure I understand odgi any better, but I have it working on the havarti server. I also completed other setup-related tasks and finished the calyx tutorial. I have just finished programming a simple (certainly suboptimal) 2x2 matrix multiplier, that seems to work! (My testing was less than rigorous).
2. How much should I worry about manually optimizing the hardware? Where would be a good place for me to learn more about optimized hardware (e.g. matrix multiplication)? Also, is there any way to customize emacs on the server without affecting others' workflows?
3. I would like to check back in to see if you have suggestions on what to do next, but in the meantime I will go through the dahlia documentation and finish reading the calyx and odgi papers.

[susan-garry]

Also, is there a way to initialize data to be a negative value, either with something like 32'd-1 or "data" : [-1]" in the initialization file?

[sampsyo]

Awesome!! Incredibly cool that your matrix multiply is already working. :D

• As for understanding odgi, probably a good next place to look is in our very unpolished Python reimplementations of the node depth algorithm. We can also talk about this synchronously, but this code is probably at least somewhat intelligible and may explain a bit more what's going on with the pangenome graphs and this one particular algorithm.
• On optimizing hardware: we will hopefully get much more into this as the project progresses, but TBH I probably wouldn't worry too much about for the matrix multiply example. It's a really good question about where to learn more about making hardware go faster… unfortunately, I think this is one of those situations where there is no general-purpose advice, and everything is pretty application-specific. At a high level, it's all about parallelism—the more we can use par to make work happen concurrently, the better off we are. But how to actually accomplish that is anyone's guess.
• Customizing emacs on the server: sure, you should be able to put stuff in your ~/.config/emacs/init.el or similar! That's in your home directory, so it won't bother anyone else.
• Negative numbers: I don't think the Calyx source syntax supports negative integer literals. Maybe we should add that TBH! You can always type out the unsigned representation of the same bit-pattern as the signed number you want, but that's certainly a pain. But it should work to provide them in the JSON data input file, right? I don't think I've tried it myself, but this test data file includes a negative number.

[sampsyo]

As for next steps: we can also talk about this synchronously, but I think a good next macro-step would be getting the current node depth implementation working and making it fast. Namely:

• Try running the existing Dahlia code. You will need to look around at the branches in that repo; I think some stuff is still unmerged. Please help us merge it so everything is on the main branch!
• Make any cleanups that you like there, including to the test harness that compares the various implementations.
• Learn about what makes odgi's data format fast. Let's first try reimplementing those techniques in the Python world to demonstrate better data structures we think are feasible in hardware.
• Port those data structures to Calyx, either using our existing Dahlia implementation or by writing Calyx by hand.

[sampsyo]

We may want to replace the current testing script with Turnt's new support for multiple environments (and differential testing), documented here: https://github.com/cucapra/turnt#multiple-environments

[susan-garry]

Wednesday, June 15

1. I read the calyx and odgi research papers. I am almost done with the odgi paper, and I have not found any specific information regarding optimizing the node depth computation, but I'm starting to understand the ways in which their data representation allows for parallel computation. I have also been going through the onboarding steps to become officially hired, and as of now everything is completed except for my background check (which is 95% completed).
2. None as of now!
3. The next thing I will do is clean up the repo and merge all unmerged branches. Then I'll start familiarizing myself with the dahlia and python implementations of node depth and work on an improved algorithm (in python).

[susan-garry]

Friday, June 17

I cleaned up the repo, merged all branches, and switched to using turnt for testing. I also started going through the odgi codebase to try to figure out how their node depth implementation works, and now I'm a bit confused about what exactly it is that we're trying to do. The command that we're using to compute node depth via odgi uses a function defined in depth_main.cpp, and it does not appear to use any of the functions defined in depth.cpp. I also have no idea what the dahlia implementation of node depth is meant to compute; my guess is that it computes the node depth given two paths, one of which extends the other, but this seems like a very specific use case. Either that or it is eliding a significant amount of data preprocessing.

I think that for now we probably want to focus on what's in depth_main.cpp, so I will continue pulling on this thread and trying to understand exactly what it and the functions it calls are doing. I will also try to get a better understanding of the data representation for a graph that the odgi developers are using. Once I think I have a good idea of what is happening, I will attempt to replicate this in python.

[sampsyo]

Awesome; thanks for the update!

About navigating the odgi code: AFACIT, the connection between depth_main.cpp and depth.cpp is here:
https://github.com/pangenome/odgi/blob/e2de6cbca0169b0720dca0c668743399305e92bd/src/subcommand/depth_main.cpp#L510

Namely, that calls the chunky for_each_path_range_depth function we have been looking at here:
https://github.com/pangenome/odgi/blob/e2de6cbca0169b0720dca0c668743399305e92bd/src/algorithms/depth.cpp#L101

…which I believe comprises the core of the computation.

If you want, one good next step to consider along these lines would be profiling the code. Have you ever used a profiler before? If not, I'd be happy to pair-program to walk you through one option or the other. Profiling is a really useful way to get familiar with an unfamiliar (computationally intensive) codebase by telling you where the time is spent, which typically correlates with what matters in the computation.

My favorite profilers are gperftools, which can be extremely easy to use, or the venerable gprof. To make this interesting, we will need at least a medium-sized input file to make the depth analysis take a nontrivial amount of time to complete.

[sampsyo]

As for understanding the current Dahlia implementation: I agree that it's not obvious (we could perhaps add a bunch of comments to make it painfully clear what's going on?). It might be useful to compare to the Python implementation that is supposed to be similar, i.e., depth2.py:
https://github.com/cucapra/calyx-pangenome/blob/3c7fa710d711cbd7a7247c9b9e46d02ce235fd88/depth2.py#L16-L20

Namely, I'm pretty sure len(p_offsets) is supposed to be the number of paths—so you're right that the Dahlia implementation is hard-coded to work with exactly 3 paths. The offsets memory in the Dahlia program contains the "start index" for each path in the paths memory. (So you can think of paths as being a concatenation of all the information for all the paths.)

Finally, segments is the output. These lines in the Dahlia code:

let count = segments[index];
---
segments[index] := count + 1;

are the painfully verbose Dahlia equivalent of the Python that does this:

counts[index] += 1

I hope that helps a little bit!

[susan-garry]

It looks like the for_each_path_range_depth function does get called if we specify certain ranges of the graph for which we want node depth extracted, using the -b flag, but the command we've been using so far just computes the depth for every node (the -d flag is specified). This runs the following code in depth_main.cpp: https://github.com/pangenome/odgi/blob/e2de6cbca0169b0720dca0c668743399305e92bd/src/subcommand/depth_main.cpp#L478-L490

[susan-garry]

Wednesday, June 22

1. Well, I spent a long amount of time trying to figure out how to get the python module of odgi to work. After hours of searching, I realized I could simply download the .so files from bioconda (here). Once I was able to import the odgi module in python, I implemented an algorithm for computing the depth and unique depth of each node in a graph. Simply computing the node depth for every node in the graph is as trivial as calculating the length of a vector, so I modified the existing baseline python algorithm to compute the unique depth of each node as well, and I've started adding functionality to compute the node depth of just a specified subset of paths in a graph. The unique depth and depth of each node are identical in all of our current test cases, but I should be able to build a few simple test cases in odgi using the python module. I also began working on a python script to convert a .og file into a data file that calyx programs could take as input data.
2. Should I open an issue/bug on the odgi repo, since I was unable to get the python module to work using the provided code? I wasn't able to figure out the issue, but I think it had to do with a linking error as certain important functions like Py_Initialize() were not defined. Oh, and one of the functions in the odgi module doesn't work because its output format is not being properly converted from C to Python (though the function is technically redundant); these seem like issues the odgi developers might want to know about.
3. I will create a few test cases where a node's unique depth is different from its depth. I also need to devise a way to test the algorithms when only a subset of paths are specified; this should be relatively easy to test manually, but I'm not sure how to automate this testing since turnt relies on arguments specified by the input files, and I'm not sure if I can add extra lines to the .og or .gfa files without corrupting them, in a way (I doubt it). I could write individual python scripts which load specific .gfa or .og files and compute their node depth, specifying the arguments to node depth in these files. Alternatively, I could make copies of the files and simply specify a set of relevant paths in an input file for turnt and the python scripts to use, instead of using ARGS. I will also update the calxy-pangenome README with instructions for importing the odgi python module, and attempt to start coding the hardware in calyx (and, with any luck, automatically generating the calyx programs given a few size parameters).

[sampsyo]

Awesome!!! Nice work on sorting out that weirdness with the Python odgi bindings! I assume this is the odgi-based implementation you're referring to?
https://github.com/cucapra/calyx-pangenome/blob/d8f7c1882d748423d798ea50f1ef085a04aae0af/depth3.py

I like your idea of getting more interesting tests. I assume these will come in the form of .gfa files, right? There are (small, test-sized) examples right in the odgi repo:
https://github.com/pangenome/odgi/tree/master/test

And the tutorial also links to the much larger Human Chromosome 8 dataset:
https://odgi.readthedocs.io/en/latest/rst/tutorials/detect_complex_regions.html#get-the-human-chr8-dataset

which is ~800 MB compressed. Maybe that one would be good as a scale-up performance test!

---

Yes, filing some bugs with the odgi project seems like a great idea! The developers have signaled a desire to hear feedback from people using their stuff, so I imagine they would really appreciate bug reports—even if you're not 100% clear on what exactly went wrong, writing up a report could be very very useful. 🎉

---

About using Turnt for testing with different arguments: a couple of ideas come to mind.

1. The gfapy docs suggest that comments starting with # are allowed in .gfa files. I don't know if this is part of the standard, but we could pretend that it is!
2. Turnt allows options like ARGS to go in a "file on the side." If you put the input file into a directory, you can put an opts.txt or similar in the same directory just to contain ARGS. This is known as "directory tests" in Turnt.

[susan-garry]

Yes, that is the odgi-based python implementation I was referring to!

I have updated the Makefile to runs test on all of the .gfa files in the odgi test directory; there also appear to be some .bed files that we might want to make use of at some point.

I also added support for testing on the Human Chromosome 8 dataset, but that takes so long for even odgi to process that I am not including it in the rule for make test. Definitely looks like it would be good for a scaled-up performance test though!

I have also now filed the bug reports with the odgi project and set up Turnt testing (though in a somewhat different way... I'll talk more about this in my update for today).

[susan-garry]

Friday, June 24

1. I largely worked on setting up a testing framework, keeping in mind that we also need to test node depth over a subset of paths in a graph. I make a PR request which details my strategy for this, but essentially it involves a directory called subset-paths for {base}.paths files, specifying a subset of paths for some graph, and corresponding {base}.txt files, specifying the .og file which {base}.paths corresponds to. (This directory gets its own turnt.toml file). I also worked on a command line parser for depth.py (renamed from depth3.py) and created a few test cases for the --subset-paths option.
2. Do you have time to take a look at the PR? It's not strictly necessary but I would appreciate the feedback if you have time! (I know we only talked about looking at the makefile, so I'm sorry for the somewhat bloated PR. I'd forgotten how long ago it was when I last typed git push since I'm the only person writing code for the calyx-pangenome repo at the moment).
3. Turn it into calyx! I'm excited to finally get to the meat of this node depth project!

[sampsyo]

Awesome!!! I will definitely comb through the PR sometime soon—and totally cool that there's a lot in it. Granular PRs are always even more fun to review, but I totally don't mind coping with a bigger one, and the circumstances seem to warrant it.

And yeah! Diving into the Calyx stuff sounds great. You might consider starting by writing Calyx code from scratch, but that might be a total non-starter and generating code might be the right thing from the get-go. For the nitty-gritty infrastructure for Calyx code generation, there are basically 3 options:

1. Use Rust and the Calyx library directly. You'll build up the IR in memory using the ir module—for example, directly constructing a Component object and filling it with cells, groups, control, and so on.
2. Using anything, just generate Calyx as text files. Couldn't be simpler! May or may not be annoying to get the syntax right.
3. Using the calyx-py Python library. This is a pure-Python module for constructing Calyx ASTs as Python objects. It can then serialize these ASTs to Calyx text files. If you like Python, this will probably be less annoying than generating strings directly. But there's no guarantee that this is complete/up-to-date; there may be missing features in the AST that we will need to add.

[rachitnigam]

Directly constructing things using the ir module is a little more challenging than using the calyx-py library. If you take that route, feel free to ask questions about how things work!

[sampsyo]

I was thinking a little bit today about the medium-term future of this project! Here are the next steps I can currently visualize:

1. Hammer out a very fixed-function Calyx implementation of the node depth computation for a given size (inspired by our current Dahlia implementation).
2. Generate this Calyx implementation with a parameterized size so we can process arbitrary input graphs.
3. Pick a second odgi analysis to implement. A super simple-seeming option might be odgi degree. More ambitiously, we could see what the expensive parts of odgi viz are and implement those (although literally producing a bitmap image is certainly out of scope).
4. Extend the generator to work for both node depth and the second example chosen above.
5. Invent the DSL! Using this existing generator as an inspiration, let's design a little tiny language that can express both—and rejigger the generator above as a "compiler" for this language.
6. At this point, it would probably be a good idea to get our generated Calyx code running on a real FPGA so we can compare performance with the CPU implementation. Then the work of performance optimization can begin!

So much to do! But it also feels like some kind of initial results are within our grasp.

[susan-garry]

Monday, July 26 (late update)

1. I've cleaned up the test infrastructure and started learning rust (mostly using Rust by Example).
2. Should I request another review, or go ahead and merge the changes? (We will still be able to look at the comments once it is merged).
3. Continue learning rust, and fix a minor bug in the interpreter with respect to formatting calyx output properly. I will also start learning the IR representation for calyx so that I can generate calyx programs directly in rust.

[anshumanmohan]

Monday, Oct 3

Here's what I've been up to this week:

• Got close to wrapping up the mini-task of getting us a Docker machine with support for resource estimation via Vivado. A bit of a wrap-up thread is here.
• Taught myself a little more about MapReduce and Calyx's support for it. I found the MrXL tutorial and I'd like to chat about whether that's worth looking at for our compiler-to-be.
• Before we meet tomorrow, I'll do some further work on my survey of odgi commands. When I say something looks parallelizable, I'd like to get a little deeper into the weeds and say, precisely, what the map and the reduce would be.
• Minor, but Susan and I have been working on a better working analogy for understanding nodes, steps, and paths in odgi graphs. We'll run this past the rest of you if there is time.

Relevant to the above, a few questions for others:

• I'm wondering if getting Vivado via fud is looking tenable. If so, I'd like to lean on that and close out the Docker story.
• Thoughts on MrXL?

In the coming week, I propose to:

• Publish a push-button Docker image that builds and tests everything we have. Maybe share it with Panorama.
• Finish my survey of odgi commands and come up with a few solid proposals for nodewise- or pathwise-parallel implementations. Maybe share this with the odgi team.
• Overdue: review Susan's PR re: readme

[sampsyo]

Thanks for the update!!

I'm not 100% sure what "Thoughts on MrXL?" means 😃 but just as a little background: MrXL is a little "demo" frontend we made as a kind of tutorial for how Calyx works from a DSL implementor's perspective. (Fun fact: the intro to the Calyx paper, in one draft, walked through the construction of the MrXL frontend. We ripped it out for the simpler examples that are there in the published version.) It's a vague to-do item to write up a prose tutorial around that code, someday.

[susan-garry]

Tuesday, October 11

This week, I've been working on creating a command line interface for the hardware accelerator. My original goal was to improve the structure of the repo to make it easier to work on node degree, and a command line interface would make it easier to run the accelerators from anywhere within the repo (e.g., in the test directory). The basic idea is to have a central command, pollen, which calls config_parser and run from depth/main.py. The job of depth/main.py is to merge the inferace for node depth's accelerator generator and data parser.

Currently, the command line interface looks something like pollen depth --action=[run/parse/gen], where the default --action is gen. (The -a, -n, -e, and -poptions still allow the user to specify the hardware parameters, but now the -n, -e, and -p flags override the -a flag. For example, if we want to test a single processing element, we can use -a to automatically infer max_steps and max_paths, but set -n=1 to create an accelerator with just one PE).

• The gen action generates a hardware accelerator according to the given specifications.
• The parse action takes an odgi file (-f <filename>) and outputs a calyx input file. The same options are used to specify the dimensions of the input data.
• Lastly, the run action takes an odgi file or a calyx input file (-f <filename>), a node depth accelerator (-x <filename2>), and runs the input file through the accelerator. It generates a calyx input file if <filename> is a .og file, and generates a node depth accelerator if -x is not specified.

I am still trying to sort out a few issues:

• What would be a good alias for --action? I'm already using -a for --auto-size, but I could change this. I could use a captial -A for --action, or a random (unused) letter? Or, should I create two separate flags instead of --action: -r for run and -d for parse [data]?
• Is there a better command name than pollen? I figure we might want to reserve this for running code written in the (future) DSL.
• What should I do with the temporary files sometimes generated when --action=run? If I store the files in a default directory, like tmp/shg64, then multiple people running the command on a server simultaneously would run into trouble. However, storing the files in the current directory could clobber existing files. I will add an addition command line option like --tmp-dir that allows a user to specify a directory to store the generated files, but I'm still not sure what the default should be. I think that fud puts temporary files in the machine's temporary directory, so I will start by searching through the fud directory to see how it deals with temporary files.

Also, related to my initial task of cleaning up the repo, I was thinking of creating subdirectories in test for depth and degree so that we don't have to duplicate the test files. However, turnt assumes that turnt.toml is in the same directory as the test file. For example, turnt ../ex.og will try to use ../turnt.toml, and if the file doesn't exist, it throws an error. As far as I can tell, we could:

1. Duplicate the test directory for each command. This could work well if we only write accelerators for a relatively small number of commands.
2. Modify turnt to check the current directory if it doesn't find a turnt.toml file in the same directory as the test file.
3. Don't use turnt.

This upcoming week, I would like to

• Finish the basic command line interface
• Refactor the node depth generator to take a file with a processing element as input; modify the command line interface to allow a user to pass the file as input
• Overdue: Get Anshuman's docker working on gorgonzola

[sampsyo]

Super awesome! I really like the idea of cleaning up the scripts a bit so they act more like a cohesive command-line tool. 😃

A couple of thoughts on those "UI" topics you mentioned:

• All of the options you mentioned sound just fine, but for whatever reason, my intuition is leaning toward separate flags: like --run, --parse, and --gen. That would at least be pretty readable!
• I like the name pollen. Perfectly nice name!! 😁
• For temporary files, I probably would recommend using the system's temporary directory by default. The Python stdlib has TemporaryDirectory for this purpose, which makes this pretty convenient. I also like the idea of having an override, though, just in case the user wants to look at the temporaries manually!

[sampsyo]

For the testing thing: that's an interesting problem. Maybe these are both silly/unworkable, but would either of these work?

• Just use (even) more envs in the turnt.toml? That could get messy, I guess.
• Use symbolic links (instead of copies) to make the relevant .og files, etc., appear in multiple directories.

[anshumanmohan]

Thanks, Susan! Excited to play with this soon. I don't a ton to add beyond Adrian's suggestions. The temp file thing looks neat indeed!

I see there may be a slight misunderstanding re: Susan's pollen question. I think we all like the name, but Susan was asking about grabbing some other name for this CLI and reserving the punchy name for the DSL itself. You could consider exine, which has a biological link to pollen. You could also just overload the command with flags (where eventually not having a --cli flag will mean "please just run the DSL").

[sampsyo]

Ah yeah, good point! Seems like a pretty cool name for the executable too. 😃

[anshumanmohan]

Monday, Oct 17

Last week Since my last post:

• Worked with Susan to get calyx + odgi + pollen figured out in Havarti and in Docker. Also got the readme merged in.
• Minor, but got the pollen logo into the readme and created a package release for our Docker image.
• Worked through the odgi commands chop, crush_n, and matrix_writer to study them for parallelization and pipelining opportunities.

Questions for the others:

• I've found something weird/funny in each of the three algorithms, and I'd like ~15 mins to run over them in our meeting before asking your thoughts. In some cases I am quite confused by what odgi is doing, and will advocate that we veer off the path of l’œuf.
• I'm also hoping we can discuss Filament-style pipelining opportunities, and how you'd advise I go about spotting them.

This week:

• The calyx + odgi + pollen setup within Docker has a missing piece: resource estimation via fud's remote facility. Get that going. Overdue.
• With a Github package release comes the work of setting up a workflow that automatically builds and pushes the package in reponse to changes in the repo. I need to decide how often this happens, and I need to tinker with it to get it right. Backburner.
• Significant follow-up work following our discussion about the three algorithms.

[dc854]

1. I have been mostly looking through the work that Susan has done and thought about how it could be utilized for degree.
2. I ran into an issue using the Docker. I wasn't going to use it this week but was just trying to set it up, so might have questions on if I was using it correct.
3. I'm trying to get the Docker working, so I don't have to any additional installation on the server. In addition, I'm going to try to work on an unoptimized version of degree.

[susan-garry]

Tuesday, October 18

Last week:

• Work on the command-line interface and created a pull request, adding the --tmp-dir flag and changing --action=[gen/parse/run] to -g/--gen, -d/--parse-data, and -r/--run. As a result, I will probably want to eliminate the -f flag for specifying the filename (-d and -r could be modified to accept an argument).
• Working with anshuman, got odgi python binding working in Docker.
• Updated the readme (with a lot of great feedback and edits from anshuman)

Questions:

• Should I eliminate the -f flag?
• I am still trying to decide how to restructure our testing setup to make it easy to test multiple odgi subcommands (e.g., node depth and node degree). Adrian's suggestion to use symlinks worked like a charm (recall that turnt expects turnt.toml to be in the same directory as the input files), until I decided that we probably shouldn't regenerate the .og files from the .gfa files each time we ran the tests.
  Digging further, I realized the the reason we currently generate so many .og files is that an odgi file cannot be passed as an argument to turnt. Turnt reads the input file to check for, among other things, override commands and ARGS, by .og files are not encoded in utf-8 format and therefore cannot be read. The issue for testing is that I cannot simply create symlinks to the .og files; I would have to create symlinks to the .gfa files and generate .og files in each subdirectory. Using {base} does not solve the problem because {base} does not include the full path to the file. For example, the {base} of test/note5.gfa is note5, and note5.og cannot be substituted for test/note5.og.
  The 4 possible solutions I have come up with so far are:
    1. Define a .txt (or perhaps .tst) file for each .gfa file. These files will contain a single argument: the .og file to use. This would be easy to copy and paste into different subdirectories for each of the odgi subcommands but would be a bit messy.
    2. Edit turnt.toml to hardcode the path from the root directory to the .og files. For example, depth/turnt.toml could contain command = cat depth/{base}.og. This is annoying because now turnt can only be run from the root directory.
    3. Use the --args flag to specify the directory which contains the odgi commands. Then the file above would read command = {args}/{base}.og. The only downside is that the --args flag must always be specified, no matter which directory you are in.
    4. Simply regenerate the .og files each time we run turnt.
  None of these solutions are particularly satisfying to me, and since this affects everyone else's work, does anyone have an opinion about these possible solutions or (I hope) a better one?

This week:

• Finish the command line interface
• Restructure the testing setup to accommodate other odgi subcommands
• Restructure the node depth accelerator generator to use subcomponents for the individual node depth accelerator. Then alter the cli so that the user can specify the file which defines this subcomponent.
• Modify the node depth generator to utilize multiplexing - i.e., use the same processing element to compute the node depth of multiple nodes

[sampsyo]

Awesome!! Here are some very quick thoughts:

• It doesn't seem crazy to get rid of the -f flag! Especially if -r requires a file argument anyway… then it seems nicer to not have a separate flag for that.
• Wow, super frustrating problem about not being able to use .og files as test inputs for Turnt!! I think it wouldn't be too hard to just hack Turnt to allow binary files… that is, to provide some kind of mode where it doesn't bother trying to open the file to look for ARGS: or whatever. If we did that, do you think your life would be easier? If so, I could give it a shot here…

[susan-garry]

This all sounds good to me. The -f flag is now history (I updated the pull request, then merged it, but feedback from anyone is still welcome!). As for Turnt, I think a mode where Turnt doesn't try to open the test input would be very helpful. If you're busy, I could also take a look at Turnt and try adding a flag that prevents it from opening input files?

[sampsyo]

Awesome. I'll make a note to look into this Turnt feature and we'll see how quickly I can get to it…

[anshumanmohan]

Sorry, folks, but I haven't been able to work on Pollen this week. I set aside time for it, but eventually lacked the discipline to stay away from the paper 😅 The good news is that the end is in sight: unless something truly dramatic happens, we'll submit it this Saturday. Then I'll be back here 120%!

[anshumanmohan]

Monday, October 31

Hello all, I'm back from paperland!

Last week:
Worked on the PIFO tree paper.

Questions/thoughts from that work:
No questions that are germane here, but I just want to say that I'm so very grateful for your patience!

This week:

1. I spent today working through the implementation of depth in Python and in Calyx. Nice stuff, all!
2. Over the rest of the week I'd like to cook up an implementation of crush in Python and in Calyx.
3. I'll pay attention to things that look like boilerplate and could be lifted.
4. I'll pay attention to opportunities for Filament-style pipelining. To briefly review, Rachit suggested that I use Calyx to generate a stream of work, and then have each "computer" peel off tasks one by one in a pipeline. It will take me some time to actually learn Filament, so I want to take a moment to convince you all that this is a good idea before spending that time.

[dc854]

11/1:

1. I spent the week looking at degree and trying to finish the python implementation. I am currently looking at testing the output to see if my understanding is correct. I have also began to look at Susan's degree implementation in Calyx and seeing how it can be used for degree.
2. No questions at the moment.
3. I'm going to continue to look at Calyx for degree and see if there is a difference between it and depth.

[anshumanmohan]

Super! Also feel free to ask about questions about setting up turnt. Here is the repo again: https://github.com/cucapra/turnt

[susan-garry]

Tuesday, November 8

I've been working on getting multiplexing working for node depth, which was easier said than done. I (think I) caught a couple bugs with calyx, one involving the compilation of the ref keyword and the other involving the interpretation of the invoke keyword (the amazing Griffin seems to have already solved the second one!), and now I'm dealing with another oddity...

Since I'm having issues with the ref keyword, I implemented multiplexing by invoking components the "hard way." This seems to be working, somewhat. I just tried running the code through the interpreter, and it works! However, running the code through verilator produces a stack overflow error for larger files (DRB1-3123.og and LPA.og). Running the code through icarus-verilog always produces the following error:

ERROR: Invalid Numeric Type: Memory contains the value: `0xx', which is uninitialized. 
This happens when the Calyx design attempts to read a port that is not connected to anything. 
Try to generate a VCD file using `--to vcd` and look for signals that are not driven in a given cycle.

I will try looking into this; my hope is that the bugs are related, and fixing the bug with icarus verilog will help provide insight as to why verilator is producing an error.

While I was catching bugs in the code, I also caught one in my stomach. I seem to be getting better now (fingers crossed), so hopefully I can track down some of the issues with verilator and icarus verilog this week. If I figure out what is causing these bugs (or need a break from trying to solve them), I think these are my next steps:

• Merge some of the node depth optimizations from other branches, and attempt to implement other optimizations
• Take measurements to test the effectiveness of multiplexing (I'm not sure how to compare this data across odgi examples; I could calculate the percent difference between the actual Work per Processing Elements and W/N, where N is the number of processing elements. It might be reasonable to compare the percent difference across multiple examples?)
• Restructure the node depth generator to accept as input a class that defines (1) node_depth_pe, to generate the processing element; (2) parse_data, which creates input for the processing element. The two functions are linked, so it makes sense to keep them in the same file; keeping them in the same class allows us to create a 'default' class, and optimizations can override parse_data as needed. (Side note: I just realized while refactoring node depth that our language will also have to provide support for transforming odgi graphs into input for those accelerators.)

[rachitnigam]

The icarus error indicates that there is some part of the design that is using uninitialized signals somewhere. For example, if you use .out on a memory without providing .addr0 signal. This can be difficult to find but one known issue may be contributing to it: calyxir/calyx#1215

One possible to catch problems is running: fud e -s futil.flags ' -p validate -p remove-comb-groups -p validate' --to icarus-verilog <file>. This will run the remove-comb-groups pass and check for the aforementioned problem.

If this doesn't provide any errors, then the problem is somewhere and you have to look at the VCD file to figure out where it comes from. This bug is not caught by Verilator or the interpreter because they automatically assign 0 to all missing ports.

[rachitnigam]

However, running the code through verilator produces a stack overflow error for larger files

Can you paste the log of the fud execution that generates the stack overflow error? Not sure where that comes from but if its in the compiler, it can (and probably needs to) be fixed

[sampsyo]

Yeah, the Verilator stack overflow error sounds quite worrisome… if it's in the generated (Verilated) executable, that would be very very interesting indeed.

Take measurements to test the effectiveness of multiplexing (I'm not sure how to compare this data across odgi examples; I could calculate the percent difference between the actual Work per Processing Elements and W/N, where N is the number of processing elements. It might be reasonable to compare the percent difference across multiple examples?)

I agree it would be hard to compare across input graphs. But maybe it's OK not to? That is, we could just compare "multiplexed" vs. "non-multiplexed" conditions for each graph. I'm imagining a bar chart where the x-axis is odgi input graphs, and each graph has two bars (for the two conditions). The y-axis is performance/efficiency: i.e., cycles or something. Would that make sense?

[susan-garry]

I created an issue in calyx (#1273) with the log of the fud execution which produces a stack overflow issue. I also tested it using icarus-verilog and got an essentially identical error message.

[anshumanmohan]

Nov 14

Last week I worked on crush.

• I've implemented in Python a version of the algorithm I proposed during our previous meeting.
• I don't quite do it in the spirit of binary sort, but the essence is captured: I create small chunks of work of size k, and I double k repeatedly until the entire sequence is looked at.
• Only one of the original graphs has runs of N, so testing crush against those has begun to feel pretty silly. I'm going to build up a better testing suite early tomorrow.

Questions.

• The algorithm is quite contrived. This is perhaps okay as we are just trying to explore a connection to Filament... all the same, I'll point out the silliness during our meeting tomorrow and ask your thoughts.
• This exploration led me to notice that the ODGI python bindings only supports "read" operations and operations that build a graph from scratch. Modifying a node in place is not supported. They document this in their code. Worth chatting about this to see how we'll need to change our SOP.

Coming week.

• Modify the algorithm based on the group's feedback.
• Generate crush in Calyx.
• Chat with Susan to see if her parallelism efforts can be applied here.
• Chat with Rachit to see if we can connect to Filament, as contrived as our algorithm is.

[susan-garry]

In answering Adrian's question from our meeting yesterday, it looks like odgi-api.cpp is part of the new python bindings, odgi_ffi. Looking at this file, it seems that the new python bindings don't even allow you to create a graph from scratch! (I think you will want to use the old python bindings when you create your new test cases).

The old python bindings also, curiously, have a function called divide_handle which seems to do the same thing as chop. This might not help with crush, but I thought that I would make note of it since you mentioned trying to use chop to implement crush.

[sampsyo]

Got it; thanks for the follow up! Maybe the thing to do for now is to emit (text) GFA files instead of relying on the odgi API for output?