Skip to content

Latest commit

 

History

History
302 lines (244 loc) · 12.3 KB

notes.org

File metadata and controls

302 lines (244 loc) · 12.3 KB

Hello, World!

print("Hello, World!")
std::cout << "Hello, World!" << std::endl;

Hugo and ox-hugo

Here’s the customary how I made this site using X post.

This site is built using Hugo and ~ox-hugo~.

The source is written in Org mode, which is converted to markdown by ox-hugo. To get started yourself, check out the initial commit of the source repository and build from there.

Some notes:

  • I’m using the Hugo-coder theme.
  • Since the conversion from Org to markdown is done using an Emacs plugin, the emacs folder contains a simple init.el to import ox-hugo and a function to export all *.org files in the repository apart from those inside the emacs folder itself.
  • The makefile contains the build-content rule to call the conversion, and build-site to invoke Hugo. Just running make will do both of these and serve the site locally.

1st law of Procrastination

Important deadlines require important procrastination.

Data should be reviewed

Experiments and their analysis should be reproducible, and all data/figures in a paper should be reviewable. Pipelines (e.g. snakemake files) to generated them should be attached to the paper.

I’ve asked for automated scripts to reproduce test data on 3+ github repositories now, and got a satisfactory answer zero times:

  • WFA: smarco/WFA2-lib#26

    Link to a datadump on the block-aligner repository. Good to have actual data, but exactly how this data was created is unclear to me.

  • WFAlm: jeizenga/wfalm#6

    Some manual scripts to be invoked – high probability of manual error, and I have to use tools I do not fully understand since I have not used them before.

  • BiWFA: smarco/BiWFA-paper#1 (pending)

RTFE

Read The F*ing Error
  • When you complain about an error without reading it first.
  • When you assume you understand the problem halfway through reading the error, and only after more debugging you realize you failed to read properly.

Motivation

It’s not the need for faster software that motivates; it’s the mathematical discovery that needs sharing.

Benchmark attention points

Benchmarking is harder than you think, even when taking into account this rule.

This post lists some lessons I learned while attempting to run benchmarks for A* pairwise aligner. I was doing this on a laptop, which likely has different characteristics from CPUs in a typical server rack. All the programs I run are single threaded.

Hardware

Do not run while charging the laptop
Charging makes the battery hot and causes throttling. Run either on battery power or with a completely full battery to prevent this.
Disable hyperthreading
Completely disable hyperthreading in the BIOS. Multiple programs running on the same core may fight for resources.

CPU settings

Pin CPU frequency
CPUs, especially laptops, have turboboost, (thermal) throttling, and powersave features. Make sure to pin the CPU core frequency low enough that it can be sustained for long times without throttling.

In my case, the performance governor can fix the CPU frequency. The base frequency of my CPU is 2.6GHz, so that’s where I pinned it.

sudo cpupower frequency-set -g performance
sudo cpupower frequency-set -u 2.6GHz
sudo cpupower frequency-set -d 2.6GHz

Note that even with a pinned CPU frequency, thermal throttling can reduce it.

Pin program to core
Make sure your program only executes on one core. Do this using e.g. 
taskset -c 0 <shell invocation>

When running multiple experiments in parallel, use distinct ids instead of 0.

Software

Use a low job niceness
At any point in time, multiple jobs need CPU resources. Use a low job niceness (like -20, needs root) to give your experiment a higher priority. As an example, input (keyboard) and audio processing usually runs with niceness -20.

This should reduce the number of (kernel) interrupts to your program.

nice -n -20 <command>
Do not use Snakemake for benchmarking memory usage
It turns out that Snakemake’s polling-based memory-usage measurement can be very imprecise. Apart from the first 30s (or really 15s actually), it polls every 30s. This means that for programs whose memory usage grows linear with time, the measured memory usage of can be off by a factor 2 when it runs for 59s.
Limit the number of parallel jobs
Memory bound programs share resources, even when running on disjoint CPUs. In my case, using all 6 cores (running 6 benchmarks simultaneously) gives a 30% slowdown compared to only using 1 core at a time (on some specific experiment). Using 3 cores simultaneously gives only 10% slowdown, which is acceptable in my case.

A* variants

These are some quick notes listing papers related to A* itself and variants. In particular, here I’m interested in papers that update $h$ during the A* search, as a background for pruning.

Specifically, our version of pruning increases $h$ during a single A* search, and in fact the heuristic becomes in-admissible after pruning.

Changing $h$

The original A* paper has a proof of optimality. Later papers consider this also with heuristics that change their value over time.

  • Original A* paper [cite:@astar-hart67] does not consider a changing heuristic.
    • A later addendum [cite:@astar-correction-hart72] removes the need for the heuristic to be consistent in the optimality proof, but does not otherwise change things.
  • [cite/t:@astar-optimality-gelperin] considers that $h$ may depend on the A* state. Notation: $\hat h(n, m)$: the value of $h$ in $n$ just before closing (expanding) $m$, and $\hat h(n, \overline m)$, the value of $h$ in $n$ just after closing $m$. State: $Σ(m)$ resp. $Σ(\overline m)$. Second argument may be omitted:

    When is it neither necessary nor helpful to use this new notation, we will use the older notation with search-state dependence understood.

  • [cite/t:@asar-optimality-revisited-dechter83] comment on and extend the proof of [cite:@astar-optimality-gelperin], but are not specific about $h$ depending on the state.
  • Somewhat unrelated, a nice paper going over some tricky details regarding A* is [cite/t:@astar-misconceptions].
  • Multiple-path pruning is the technique from [cite:@artint] to remove paths going through expanded nodes to which an optimal path has been found.

Variants

There are some variants of A* for repeated searches that do incremental updates of $h$ between iterations. Note that $h$ is assumed to be admissible, and usually also consistent. Incremental A* refers to the entire class of versions of A* that reuse information between runs.

The Wikipedia page on incremental heuristic search has more information.

D* (Dynamic A*) [cite:@dstar;@dstar-focussed]
Setting: a robot is navigating and discovers new obstacles along the way. This leads to increasing (or possibly decreasing) edge weights. They keep OPEN, RAISE, and LOWER lists. $h$ is assumed to the distance to the end in the so-far explored graph.
Adaptive A* [cite:@adaptive-astar]
Setting: repeatedly find shortest path to a fixed set of goal states, but varying start states. Input: a consistent heuristic $h$. (I’m not sure where/why consistency is needed.)

Intuitively, it uses that after making a search from $s$, we know that all states close to $s$ must have a distance that is not much smaller than the distance from $s$.

The main insight of Adaptive A* is this: after running one iteration from $s$ to $t$, let the distance from $s$ to $t$ be $h^*(s)$, and let $g(u)$ be the shortest distance from $s$ to $u$ found so far. Write $g^*$ for the distance from $s$, $h^*$ for the distance to $t$, and $f^*$ for their sum. By the triangle inequality, $h^*(s) \leq f^*(u)$. We get \begin{equation} h^*(s) \leq f^*(u) = g^*(u) + h^*(u) \leq g(u) + h^*(u). \end{equation} Rewriting gives $h^*(u) \geq h^*(s) - g(u)$, which we can use as a new value for $h$ that is possibly better than the user provided value.

Edge weights may increase over time.

Real-Time Adaptive A* (RTAA*) [cite:@real-time-adaptive-astar]
Same setting as Adaptive A*, but now the model is a robot searching the grid. There is a limit on the lookahead and movements it may make.

After increasing edge weights, they show that the heuristic remains consistent.

Generalized Adaptive A* (GAA*) [cite:@generalized-adaptive-astar]
Can additionally handle decrements in edge weights and changes of goal state. Input: a consistent heuristic $H(s, t)$ for any pair of states, that additionally satisfies the more general triangle inequality.
D* Lite [cite:@dstar-lite]
Again models a robot moving around.

Conclusion

While there are many methods that (implicitly) modify $h$, their setting is usually in that of changing surroundings, repeated searches, or constrained to a single moving robot. All these are different from our case, where we are able to increase $h$ during a single search for a single shortest path. Further, most variants keep a more complicated state to handle the updates than that of a single A*.

IGGSY 22 Slides

These are the slides Pesho Ivanov and I presented at IGGSY 2022 on Astarix and A*PA.

Drive: here

Pdf: here

Bidirectional A*

These are some links and papers on bidirectional A* variants. Nothing insightful at the moment.

small lecture
introduces $h_f(u) = \frac 12 (π_f(u) - π_r)$. Not found a paper yet.
An Improved Bidirectional Heuristic Search Algorithm (Champeaux 1977)
introduces a bidirectional variant
Bidirectional Heuristic Search Again (Champeaux 1983)
fixes a bug in the above paper
Efficient modified bidirectional A* algorithm for optimal route-finding
Didn’t read closely yet.
A new bidirectional algorithm for shortest paths (Pijls 2008)
Actually a new methods. Seems to cite useful papers.

There 2 papers that cite this one may also be interesting.

Revised Oxford Bioinformatics latex template

I made an improved version of the Oxford Bioinformatics latex template. See the Github repository.

list

  • Post on suffix array construction algorithms
  • read Giulia Giodo paper
  • read Paul’s practical vs theoretical approach paper