Hacker News Reader

moabon Graph Processing on FPGAs: Taxonomy, Survey, Challenges

Here are a few references that solve problems on very large graphs:

[1] implements work-efficient parallel algorithms for a list of fundamental graph problems. They report times on a O(200B) edge graph on a single multicore.

[2] reports distributed running times for BFS, connectivity, PageRank, and SSSP on a large number of distributed hosts. The times are usually slower than the single-machine times, despite using two orders of magnitude more threads.

[3] Reports connectivity times on a truly large graph that is not publicly available (several trillions of edges).

My feeling is that unless you are at FAANG or a big national lab, the largest graphs that will show up in practice (today) are on the order of billions of edges, and can be solved quickly using single-machine multicores.

[1] https://arxiv.org/abs/1805.05208

[2] https://www.cs.utexas.edu/~roshan/Gluon.pdf

[3] https://arxiv.org/abs/1807.10727

moabon Graph Processing on FPGAs: Taxonomy, Survey, Challenges

Any insight on why this paper was posted? What graph algorithms are people in the field interested in solving on FPGAs/GPUs/other accelerators? Unfortunately I usually see the same cluster of (toy) problems solved time and again (BFS/BC/PageRank/(negative)SSSP, usually all using label-propagation style vertex-centric codes). This survey interestingly enough reports some results for maximum matching (approximate?), although it does not provide many details on the result.

moabon Removing Array Duplicates

Semisorting, and then running a filter to remove duplicates (which will be consecutive after the semisort) can solve this problem in O(n) expected work & space and O(log n) depth w.h.p. AFAIK the approach is reasonably practical as well. Note that the algorithm is not in-place.

Paper: https://people.csail.mit.edu/jshun/semisort.pdf

moabon Integer multiplication in time O(n log n) [pdf]

This very recent paper shows a matching (conditional) lower bound of \Omega(n\log n): https://arxiv.org/abs/1902.10935 (the hardness is from a conjecture in network coding).

moabon Top-down performance analysis methodology

Thanks for the reply and the pointer!

moabon Top-down performance analysis methodology

I wish the author had explained how he went from identifying that the issue is stalled references to DRAM to the CYCLE_ACTIVITY.STALLS_L3_MISS performance event. Similarly from DRAM_Bound to MEM_LOAD_RETIRED.L3_MISS_PS. My complaint is that there's still a lot of magic here that requires carefully reading the Intel manuals that is elided in this post. That said, thanks to the author for the post---it is still very useful.

Edit: the author has another post that covers this information https://dendibakh.github.io/blog/2018/06/01/PMU-counters-and...

moabon What Happened to the 100000 Hour LED Bulbs?

Some fun reading on the topic of long-living light bulbs: https://www.tildedave.com/byron.html

Edit: the source is not mentioned anywhere. This is an excerpt from Gravity's Rainbow.

moabon Ask HN: I've been a programmer for 6 years, and I can't solve basic CS problems

The point of studying data structures and algorithms that you may not use on a day-to-day basis is that they make you learn to think abstractly about problem solving. That is the whole point of getting an undergraduate degree in CS. I'm sorry that you have trouble with this stuff OP, it would be a good idea to do the cs50 course with your wife until you're comfortable with this stuff. I'm sure it will pay dividends in your future.

moabon Two men are trying to become the first person to cross Antarctica alone

The same thing could be said for many costly (in terms of either time or money) journeys: hiking the AT, biking across the world, to name two. In these cases, others have made these voyages thousands of times before, but that doesn't stop people from making these trips.

By the way, I think you're misreading the piece---I don't get the impression that these men are making these trips for vanity.

moabon Cimple: Instruction and Memory Level Parallelism

Another relevant paper on low MLP in this case shared-memory graph algorithms (http://www.scottbeamer.net/pubs/beamer-iiswc2015.pdf). It would be interesting to see whether Cimple can significantly improve performance for graph algorithms (the paper does mention it as a potential use-case).

For anyone curious, I'm not affiliated with the authors of the paper. It's scheduled to appear at PACT'19. AFAIK the code is not publicly available yet.

moabon Broken Time: “Nardis” and the Curious History of a Jazz Obsession

Really excellent article, thanks for sharing it on HN. The Ralph Towner recording from Solo Concert that the article mentions is also brilliant:

https://www.youtube.com/watch?v=e66mkcPsXVo

moabon Big Tech’s Hot New Talent Incubator: Community College

I think university experiences are bi-modal. If you're going to an essentially unranked university with very poor professors/a non-existent graduate program, you'd probably be better off going to community college and saving an order of magnitude in tuition. On the other hand if you're going to a, say, top-25 school, the price tag is probably worth it and opens the door to graduate schools and research mentorship that you can't find anywhere else.

moabon Ask HN: Has Google search becomes particularly poor in past few months?

Well, I imagine they use metrics like how many pages you sift through before selecting a link (presumably the page you were looking for), or whether you had to modify the search. As some other posters have said, observing a lift in 1% for these kinds of metrics can hide a massive loss of quality for niche queries or user groups. I imagine folks internally don't just look at aggregate stats before pushing changes, but refine metrics based on the type of query or the type of user.

moabon OpenBSD disables Intel's hyperthreading due to security concerns

It's still important to hide latency and saturate the memory controllers for programs with irregular memory accesses (e.g. graph algorithms), although the difference is not 2x, but something more like 10-15% over running without hyper-threading.

moabon “SKAM,” the Radical Teen Drama That Unfolds One Post at a Time

You won't have to worry about it if you get them addicted to books from a young age!

moabon Team Rocket Drops ‘Breakthrough’ Family of Consensus Algorithms on IPFS

Associated paper: https://ipfs.io/ipfs/QmUy4jh5mGNZvLkjies1RWM4YuvJh5o2FYopNPV...

Please post any interesting suggestions on bitcoin related papers that appear to have some theoretical content, or present simple ideas that could be proved secure. PoS seems to be plagued with lots of 40-50 page whitepapers that are not very easy to read, with the above being a nice exception.

moabon An Introduction to Hashing in the Era of Machine Learning

Some extra experimental evaluation of learned-indices: https://dawn.cs.stanford.edu/2018/01/11/index-baselines/

moabon In Switzerland, it's now illegal to boil a live lobster

Thanks for the explanation. My misunderstanding.

moabon Curry spice turmeric boosts memory by nearly 30%, eases depression, study finds

About a half-teaspoon or so of turmeric, and about a teaspoon of black pepper. A teaspoon of black pepper might be a bit aggressive, so adjust it to suit your taste, but my mom seems to think lots of pepper is necessary to reduce coughing/phlegm when you're down with a cold.

moabon The Hungarian Approach and How It Fits the American Educational Landscape (2015)

http://www.jurisich-koszeg.sulinet.hu/files/projekt/science/...

The first 5 pages have names that are attached to lots and lots of theorems (disproportionately in combinatorics).

moabon Against a Tax Increase on Berkeley Students

By taxing or putting extra burden on all but the students that absolutely can't afford to pay tuition or elevated taxes you're making an already sketchy financial proposition even sketchier. There were a few articles recently lamenting the declining numbers of American grad students. Measures like these are only going to cripple these numbers further.

moabon What Are We Doing Here?

It's too bad. This is a beautiful essay defending the humanities which are attacked by bean-counters from both sides of the aisle (and perhaps in the valley, too). I enjoyed the historical remarks on Tocqueville, and the Hilbert-like optimism for an ever-improving state of knowledge and therefore human affairs. We must know---we will know!

moabon A Student's Guide to Preparing for Data Science Interviews

I overheard some colleagues talking about a recent interview where a candidate with "stellar industry experience", i.e. Kaggle wins and previous ML experience at a valley company, who couldn't explain Bayes rule to them, let alone rederive Naive Bayes. While books like the one below are extremely theoretical, anyone interviewing for these kind of roles should spend at least a week or two just looking through this to see what kind of algorithms and properties are studied in theory.

Foundations of Data Science (Blum, Hopcroft, Kannan) https://www.cs.cornell.edu/jeh/book2016June9.pdf

moabon A Trillion Edge Graph on a Single Commodity Node

Very interesting paper, but the experimental section confuses me. They compare their system which preprocesses the graph into the tile-structure (a compressed representation), but none of the in-memory systems they compare against use a compressed representation. Is this comparison really apples-to-apples? If you can reduce the size in-memory of the graph by 60%, then I would expect an algorithm running on the compressed version to be faster than the same algorithm running on the uncompressed version (assuming that decoding the compressed adjacency-list is significantly cheaper than the cost of a cache-miss).

moabon IBM Building First Universal Quantum Computers for Business and Science

Marketing at IBM should read up before writing illuminating sentences like "...quantum computers will deliver solutions to important problems where patterns cannot be seen because the data doesn’t exist and the possibilities that you need to explore to get to the answer are too enormous to ever be processed by classical computers."

Necessary reading (read by my high-school age cousins, so your marketers should be able to grok it) http://www.cs.virginia.edu/~robins/The_Limits_of_Quantum_Com...

moabon A Neglected South American Masterpiece

> “I consider man a maker of noises,” the narrator declares. The omnipresent racket is obviously some kind of symbol, in the existential way: its significance may be that it has none.

Great piece, thanks for sharing. Although Bolano is quite different, I would raise his Savage Detectives as another contender for the "Great American Novel". Another book with individuals consumed by an inevitably futile quest that they pursue relentlessly.

moabon How to Partition a Billion-Node Graph [pdf]

Sorry, I should clarify: publicly accessible graphs. The hyperlink graphs are the largest I've found.

http://webdatacommons.org/hyperlinkgraph/index.html#toc1

moabon How to Partition a Billion-Node Graph [pdf]

You can compute non-trivial statistics about the entire web-graph (roughly |V|=3B, |E|=100B)on a single high-end server these days. Speaking from personal experience, a machine with > 64 cores and 1TB of RAM can compute connectivity, MSTs, and partition this graph in minutes. Are there graphs out there (with the exception of Facebook and Google's private graphs) that are so large as to be intractable without resorting to external-memory/distributed computing?

moabon Science Increasingly Makes the Case for God (2014)

I will let Lawrence Krauss, who is thoroughly more qualified to speak about what science "says", do some talking: http://www.newyorker.com/tech/elements/astrobiology-made-cas...

moabon Differential dataflow roadmap

A short answer: It's a recent approach to incremental computation geared towards data-science/db people. Imagine you want to maintain the connected components of a graph where edges are being added and removed. It turns out you can express this using dataflow and get reasonable looking runtimes (30,000 edge ins/del per second) [1]. You could probably do much better with a careful implementation of parallel union-find for just edge-insertions but part of the appeal of data-flow is that you express your computation using functional primitives like joins, maps and filters and then the incremental stuff 'just works'.

[1] http://www.frankmcsherry.org/differential/dataflow/2015/05/1...