On GPU architecture and why it matters

I had a nice conversation recently around the architecture of CPUs versus that of GPUs. It was so good that I still remember the day after, so it is probably worth writing down.

Note that a lot of the following are still several levels of abstraction away from the hardware, and this is in no way a rigorous discussion of modern hardware design. Still, from the software development point of view, they are adequate for everything we need to know.

It started out of the difference in allocating transistors to different components on the chip of CPU and GPU. Roughly speaking, on CPUs, a lot of transistors are reserved for the cache (several levels of those), while on GPUs, most of transistors are used for the ALUs, and cache is not very well-developed. Moreover, a modern CPU merely has a few dozen cores, while GPUs might have thousands.

Why is that? The simple answer is because CPUs are MIMD, while GPUs are SIMD (although modern nVidia GPUs are closer to MIMD).

The long answer is CPUs are designed for the Von-neumann architecture, where data and instructions are stored on RAM and then fetched to the chip on demand. The bandwidth between RAM and CPU is limited (so-called data bus and instruction bus, whose bandwidth are typically ~100 bits on modern computers). For each clock cycle, only ~100bits of data can be transfer from RAM to the chip. If an instruction or data element needed by the CPU is not on the chip, the CPU might need to wait for a few cycles before the data is fetched from RAM. Therefore, a cache is highly needed, and the bigger the cache, the better. Modern CPUs have around 3 levels of cache, unsurprisingly named L1, L2, L3… with higher level cache sits closer to the processor. Data and instructions will first be fetched to the caches, and CPU can read from the cache with much lower latency (cache is expensive though, but that is another story). In short, in order to keep the CPU processors busy, cache is used to reduce the latency of reading from RAM.

GPUs are different. Designed for graphic processing, GPUs need to compute the same, often simple, arithmetic operations on a large amount of data points, because this is what happens in 3D rendering where there are thousands of vertices need to be processed in the shader (for those who are not familiar with computer graphics, that is to compute the color values of each vertex in the scene). Each vertex can be computed independently, therefore it makes sense to have thousands of cores running in parallel. For this to be scalable, all the cores should run the same computation, hence SIMD (otherwise it is a mess to schedule thousands of cores).

For CPUs, even with caches, there are still chances that the chip requires some data or commands that are not in the cache yet, and it would need to wait for a few cycles for the data to be read from RAM. This is obviously wasteful. Modern CPUs have pretty smart and complicated prediction on where to prefetch the data from RAM to minimize latency. For example, when it enters a FOR loop, it could fetch data around the arrays being accessed and the commands around the loops. Nonetheless, even with all those tricks, there are still chances for cache misses!

One simple way to keep the CPU cores busy is context switching. While the CPU is waiting for data from RAM, it can work on something else, and this eventually keeps the cores busy, while also provides the multi-tasking feature. We are not going to dive into context switching, but basically it is about to store the current stack, restore the stack trace, reload the registers, reset the instruction counter, etc…

Let’s talk about GPUs. A typical fragment of data that GPUs have to work with are in the order of megabytes in size, so it could easily take hundreds of cycles for the data to be fetched to the cores. The question then is how to keep the cores busy.

CPUs deal with this problem by context switching. GPUs don’t do that. The threads on GPUs are not switching, because it would be problematic to switch context at the scale of thousands of cores. For the sake of efficiency, there is little of locking mechanism between GPU cores, so context switching is difficult to implement efficiently.
– In fact, the GPUs don’t try to be too smart in this regards. It simply leaves the problem to be solved at the higher level, i.e. the application level.

Talking of applications, GPUs are designed for a very specific set of applications anyway, so can we do something smarter to keep the cores busy? In graphical rendering, the usual workflow is the cores read a big chunk of data from RAM, do computation on each element of the data and write the results back to RAM (sounds like Map Reduce? Actually it is not too far from that, we can talk about GPGPU algorithms in another post). For this to be efficient, both the reading and writing phases should be efficient. Writing is tricky, but reading can be made way faster with, unsurprisingly, a cache. However, the biggest cache system on GPUs are read-only, because writable cache is messy, especially when you have thousands of cores. Historically it is called texture cache, because it is where the graphical application would write the texture (typically a bitmap) for the cores to use to shade the vertices. The cores cant write to this cache because it would not need to, but it is writable from the CPU. When people move to GPGPU, the texture cache is normally used to store constants, where they can be read by multiple cores simultaneously with low latency.

To summarize, the whole point of the discussion was about to avoid the cores being idle because of memory latency. Cache is the answer to both CPUs and GPUs, but cache on GPUs are read-only to the cores due to their massive number of cores. When cache is certainly helpful, CPUs also do context switching to further increase core utilization. GPUs, to the best of my knowledge, don’t do that much. It is left to the developers to design their algorithms so that the cores are fed with enough computation to hide the memory latency (which, by the way, also includes the transfer from RAM to GPU memory via PCIExpress – way slower and hasn’t been discussed so far).

The proper way to optimize GPGPU algorithms is, therefore, to use the data transfer latency as the guide to optimize.

Nowadays, frameworks like tensorflow or torch hide all of these details, but at the price of being a bit inefficient. Tensorflow community is aware of this and trying their best, but still much left to be done.

What Goes Around Comes Around: Databases, Big Data and the like

Over the years, I have the privilege of working with some pretty damn good people. One of those guys is a PhD in Database Research, used to be a professor, but apparently so passionate and so good at teaching that he eventually quits academia to join the industry.

He did an PhD in XML database, and even though XML database is completely useless, it doesn’t mean a PhD in XML Database couldn’t teach you anything (in fact, a good PhD could teach you quite many useful things). One interesting thing I learned from him was the evolution of database technology, which originates from an essay by Michael Stonebraker called What goes around comes around.

Michael Stonebraker is a big name in Database Research and has been around in Database research for a good 35 years, so you could easily expect him to be highly opinionated on a variety of things. The first few lines in the essay read like this:

In addition, we present the lessons learned from the exploration of the proposals in each era. Most current researchers were not around for many of the previous eras, and have limited (if any) understanding of what was previously learned. There is an old adage that he who does not understand history is condemned to repeat it. By presenting “ancient history”, we hope to allow future researchers to avoid replaying history.

Unfortunately, the main proposal in the current XML era bears a striking resemblance to the CODASYL proposal from the early 1970’s, which failed because of its complexity. Hence, the current era is replaying history, and “what goes around comes around”. Hopefully the next era will be smarter.

His work, among others, include PostgreSQL. Hence, after reading the essay, it becomes obvious to me why there are so many highly opinionated design decisions being implemented in Postgres.

The essay is a very good read. You get to see how database technologies evolved from naive data models to unnecessarily complicated models, then thanks to a good mathematician named Edgar F. Codd, it got way more beautiful and highly theoretically-grounded. After a few alternatives, a new wave of XML databases come back bearing a lot of complications. (Along the way, you also get to see how Michael Stonebraker managed to sell several startups, but that isn’t the main story – or is it?)

There are many interesting lesson learned. The most two interesting for me are:

  • XML database doesn’t take off because it is exceedingly complicated, and there is no way to efficiently store and index it using our best data structures like B-trees and the like.
    I learned XML databases and I was told that XML databases failed because it lacks a theoretical foundation like the Relational model. Now looking back, I think that isn’t the main issue. The problem with XML is that it allows too much flexibility in the language, so implementing a good query optimizer for it is extremely difficult.
    A bit more ironically, this is how Michael Stonebraker puts it:

    We close with one final cynical note. A couple of years ago OLE-DB was being pushed hard by Microsoft; now it is “X stuff”. OLE-DB was pushed by Microsoft, in large part, because it did not control ODBC and perceived a competitive advantage in OLE-DB. Now Microsoft perceives a big threat from Java and its various cross platform extensions, such as J2EE. Hence, it is pushing hard on the XML and Soap front to try to blunt the success of Java

    It sounds very reasonable to me. At some point around 2000-2010, I remember hearing things like XML is everywhere in Windows. It has to be someone like Microsoft keeps pushing it hard to make it quite phenomenal. When Microsoft started the .NET effort to directly compete with Java, the XML database movement faded away.
    One thing Michael Stonebraker got it wrong though. In the essay, he said XML (and SOAP) is gonna be the data exchange format of the future, but it turns out XML is still overly complicated for this purpose, and people ended up with JSON and RESTful instead.

  • The whole competitive advantage of PostgreSQL was about UDTs and UDFs, a somewhat generalization of stored procedures. Although stored procedures are soon out-of-fashion because people realize it is difficult to maintain your code in multiple places, both in application code and store procedures in DBMS. However, the idea of bringing code close to data (instead of bringing data to code) is a good one, and has a big consequence on the Big Data movement.

Speaking of Big Data, Stonebraker must have something to say about it. For anyone who is in Big Data, you should really see this if you haven’t:

The talk presents a highly organized view on various aspects of Big Data and how people solved them (and of course mentions a few startups founded by our very Michael Stonebraker).

He mentioned Spark at some point. If you look at Spark nowadays, it’s nothing more than an in-memory distributed SQL engine (for traditional business intelligence queries), along with a pretty good Machine Learning library (for advanced analytics). From a database point of view, Spark looks like a toy: you can’t share tables, tables don’t have indices, etc… but the key idea is still there: you bring computation to the data.

Of course I don’t think Spark wants to become a database eventually, so I am not sure if Spark plans to fix those issues at all, but adding catalog (i.e. data schema), and supporting a somewhat full-fledged SQL engine were pretty wise decisions.

There are several other good insights about the Big Data ecosystem as well: why MapReduce sucks, what are other approaches to solve the Big Volume problem (besides Spark), how to solve the Big Velocity problem with streaming, SQL, NoSQL and NewSQL, why the hardest problem in Big Data is Variety, etc…  I should’ve written a better summary of those, but you could simply check it out.

On “visions”


Sorry folks, this isn’t about him. This is about the other kind of vision that people keep talking about.

Over the years, I realised the word “vision” is a pretty good feature for detecting rubbish conversations. Every time when I heard somebody talking about “vision”, I almost immediately classify the conversation into the “bullshit” category, and I was almost always right.

Don’t get me wrong. I have no problem with them, it’s good for them to have a vision, really.

For example, in one of his remarkable interviews, Linus Tovralds compare Nikola Tesla and Thomas Edison, and he made the point when he said, although many people love Tesla, some name their company after him (you-know-who), Linus feels he is more “Edison” than “Tesla”. While other people enjoy looking at the stars and the moon, he enjoy looking at the path under his feet, fixing the holes on that path which otherwise he might fall into. Nonetheless, Linus has no problem with people having great visions.

Yea good guy Linus, when you make 10 million bucks a year, you wouldn’t bother to waste your neural cycles on those non-senses.

Leaders in the industry keep talking about their visions, which is totally understandable. That’s how leadership works. They need to show that they have some vision, so that people follow them, work for them (often underpaid), and help build their dreams.

That vision, however, isn’t necessarily only for others. When you are too rich, I guess it would take a grand vision (or two) to get yourself up every morning, to push yourself to work, to make you feel your life has some meaning in it.

In any case, it makes sense.

People who are building startups are probably the ones who talk about their visions most often. They need the money, they need to buy the investors, and for that they need a vision, or make up one if they haven’t got any. So for this case, it’s fine for them too, since they have a clear motivation to brag about their vision, which can be either extraordinary or total crap (or both).

The most annoying type of vision is the ones from Wannabe Entrepreneurs. Those could be mediocre engineers who are sick of their jobs but don’t dare to quit, fresh PhD students whose egos are overfed by the academia for too long, etc… I’ve met many of those. Their story often goes like this: oh btw, I got this awesome vision about improving X in Y by using Z. I think if we move fast, we will be the first. So I need to find somebody to realize this vision for me.

That’s the problem. Since when entrepreneurs are the ones who got a vision, but couldn’t do it himself, so he hires a bunch of people to do that for him?

I don’t think entrepreneurship works that way.

If you couldn’t do it yourself, why the heck would people believe that you could lead them to success?

Oh I hear you are saying that you actually could, but you wouldn’t, because blah blah blah (maybe because you are too good for dirty jobs)? Dear, like anything else in Engineering, it’s all about dirty work. It’s dirty work that drives progress. You can talk a lot about what you know (or pretend to know), but if you can’t deliver anything with your bare hands, then the joke is on you.

Of course, in some certain markets, at certain time, people with only vision and no action could still make money, and a lot of money. For instance, when the market are at peak for some crazy hype, then this kind of entrepreneurship might work. But I haven’t seen one, except some very ridiculous cases.

All in all, it’s good to have a vision. In fact I believe any serious people would have some form of vision in their particular area of interest. But the fact is nobody gives a damn about your vision. The only thing they care is your action, and results, if there is any.

So please, stop bragging about your vision. Start action. You might probably get something done in the future.

To conclude, it would be relevant to mention people who don’t bother bragging about vision, even when they have the authority to do so. Geoff Hinton once said in his lectures, that he isn’t gonna predict the future for more than 5 years ahead, because doing so is like driving on a foggy road. You couldn’t possibly see too far ahead, so you wouldn’t know behind the fog is the road or a brick wall.

Another example is Alan Turing, who said “We can only see a short distance ahead, but we can see plenty there that needs to be done.”.

And I believe he means it, really.


Truyện ngắn Nguyễn Huy Thiệp

Hồi xưa đi học, phân tích truyện ngắn là thứ mình thấy khó viết nhất. Giờ nhìn lại, thể loại này vẫn khó như vậy, nhưng vì giờ đã quá tuổi viết văn tới hơn chục năm, nên mình sẽ cố review cả vài truyện cùng lúc. Hi vọng là văn chương, sau hơn chục năm, không quá khó ngửi.


Tìm thấy quyển này cách đây vài năm, lúc đang lang thang trong mấy tiệm sách ở SG (đi mua sách tiếng Việt là chuyện mình hay làm nhất mỗi khi về nhà). Vốn ít đọc văn Việt Nam sau 1975, trừ vài quyển của Bảo Ninh, Chu Lai… nên cảm giác chung của mình là Văn thời này khá tẻ nhạt, nếu không viết về chiến tranh thì là văn tuyên truyền. Khi đất nước oằn mình đau khổ, lại còn bị đóng khung giáo điều, thì văn chương khó mà cất cánh được.

Với Nguyễn Huy Thiệp, đây là quyển đầu tiên mình đọc. Mãi tới gần đây mới đọc xong, và nói chung là rất ấn tượng. Lần tới về VN chắc sẽ tìm đọc Tướng về hưu.

Truyện ngắn nói chung là khó viết, và cũng không dễ đọc. Trong quyển này, có những truyện thực chất là tập hợp của vài truyện rất ngắn, nên mình đọc khá chậm.

Nhìn chung về nghệ thuật, mình hơi bối rối vì không biết nên đặt tác giả vào đâu. Có những truyện viết rất chắc tay, thủ pháp điêu luyện, kết cấu chắc chắn; nhưng cũng có những truyện hơi lỏng lẻo, hay thòng vào những câu triết lí đôi chút gượng gạo.

Mặc dù vậy, vẫn có thể nhận ra vài nét lớn trong văn chương Nguyễn Huy Thiệp từ quyển này.


Review sách: Doctor Zhivago

Lâu rồi không viết review tiểu thuyết. Ban đầu định viết kiểu “ngoại giao” (ờ cũng hay nhưng còn nhiều hạn chế v.v….) nhưng nghĩ lại thấy ngoại giao thì cũng không ai đọc, nên sẽ review ở mức hơi “tàn bạo”.

Doctor Zhivago không phải là sách nổi tiếng, ít nhất là mình chưa bao giờ biết tới quyển này, mãi đến cách đây 1-2 năm khi nghe Lara Fabian hát Mademoiselle Zhivago. Âm nhạc của Lara vô cùng lôi cuốn về cảm xúc, và album này bản thân nó cũng có một tầm sâu nhất định (mà có thể xứng đáng một bài review khác được), vì vậy có thể nói mình biết tới Doctor Zhivago là do Lara Fabian.


Vậy Lara Fabian thì liên quan gì tới Doctor Zhivago? Trong một cuộc phỏng vấn, Lara nói rằng khoảng năm 195x, mẹ cô xem phim Doctor Zhivago, và vì quá cảm động nên bà quyết định đặt tên cho cô theo tên của Lara Fyodorovna, nhân vật trong phim. Và đương nhiên, Doctor Zhivago, bản tiểu thuyết, chính là nguyên bản của bộ phim kia. Trong truyện, Lara Fyodorovna yêu nồng cháy và có khoảng thời gian sống chung với bác sĩ Yuri Zhivago, nên có thể gọi cô là mademoiselle Zhivago cũng được. Cái tên Mademoiselle Zhivago từ đó gắn liền với Lara Fabian, và trong một chừng mực nào đó, có thể Lara Fabian cũng tin rằng cái tên này nói lên nhiều điều về cuộc đời cô.

Bản thân tiểu thuyết Doctor Zhivago cũng có số phận đặc biệt. Ra đời vào khoảng 1955, giữa lúc chiến tranh lạnh đang căng thẳng, nhưng tiểu thuyết kể về thân phận những con người nhỏ bé trong khoảng thời gian 1900-1933, thời gian mà nước Nga trải qua những cơn chuyển mình vĩ đại: Thế chiến 1, Cách mạng tháng 10, nội chiến với Bạch vệ và hàng loạt những xung đột khác về giai cấp, lợi ích… Trong bối cảnh đó, sách thể hiện những quan điểm mà chính quyền Xô Viết đương thời không chấp nhận, nên bị cấm phát hành ở Nga. Tuy nhiên, bằng sự “giúp đỡ” của CIA và IM5, tiểu thuyết được tuồn ra nước ngoài, xuất bản và trở thành hiện tượng. CIA và IM5, vì mục đích tuyên truyền chống Xô Viết, ra sức lobby để tác phẩm này đạt giải Nobel văn học năm 1958, và chuyển thể thành phim sau đó. Mặc dù nhà nước Xô Viết không cho tác giả Boris Pasternak (vốn là một nhà thơ) nhận giải Nobel này, nhưng nhiều năm sau giải thưởng vẫn được trao cho hậu duệ của ông.

Một tiểu thuyết có “lí lịch” và bối cảnh như vậy hiển nhiên là đáng đọc?


Knowledge is a drug


Đối với một số người, tri thức cũng gây nghiện như thuốc phiện vậy. Làm nghiên cứu chắc ai cũng trải qua cảm giác bế tắc, chật vật cả vài tuần, vài tháng hay vài năm mà không được kết quả gì đáng kể. Tuy nhiên với vài người, cái sự thú vị của việc mỗi ngày lại có thể khám phá ra được một điều gì mới khiến cho người ta có thể sẵn sàng chấp nhận những “rủi ro” đó.

Đương nhiên điều đó không chỉ giới hạn trong những người làm nghiên cứu hàn lâm. Chẳng hạn đối với 1 hard-core developer thì một công nghệ mới, một framework mới hay thậm chí chỉ là một cách mới để làm một việc cứ tưởng đã thành truyền thống.. tất cả đều có thể mang lại cảm giác khoan khoái dễ chịu, và điều đó thực sự gây nghiện.

Cũng dễ hiểu khi mà nhu cầu tìm hiểu và khám phá có thể coi như là bản năng của con người. Tìm hiểu tự nhiên và xã hội, không gì khác hơn chính là mục tiêu cuối cùng của khoa học. Tất nhiên trong nhiều trường hợp, những phát hiện, khám phá kiểu như mối liên hệ của một vài tham số trong một mô hình máy tính chết dịch nào đó, có thể dường như chẳng liên quan gì trực tiếp tới tự nhiên và xã hội. Song, việc phát hiện ra các mối liên hệ logic của hiện thực khách quan bản thân nó đã khá thú vị. Điều thú vị hơn nữa là có thể vận dụng kiến thức đã có để lí giải và phát hiện ra các mối liên hệ mới, từ đó bổ túc thêm kiến thức. Vòng tròn như vậy dễ khiến người ta say mê không rời ra được.

Đương nhiên mức độ đam mê và kiên trì trong việc chiếm lĩnh tri thức là tuỳ thuộc vào mỗi người. Có người cảm thấy hài lòng với những kiến thức hàn lâm đã được học ở trường, có người eager hơn. Tuy nhiên ngay cả khi không làm việc trong môi trường hàn lâm, thì một người, nếu muốn, vẫn có thể liên tục bổ sung tri thức qua công việc (kinh nghiệm cũng có thể xem là một loại tri thức?), sách vở, và đương nhiên là các khoá học miễn phí hay có phí khác. Những người không chịu liên tục tìm tòi học hỏi, chắc chắn sẽ nhanh chóng lạc hậu và dễ bị đào thải.

Vậy nên nếu bạn có gặp người nào chí thú đi làm PhD với đồng lương quèn, hoặc là xong PhD rồi lại cày tiếp post-doc mà không chịu “go indie” (dù chắc phải đến 90% những người làm PhD nghiêm túc đều có thể nghĩ sẽ đi làm start-up), thì, ngoài những lí do “trên trời” như học giỏi quá không làm PhD thì làm gì, hay là không tìm được việc, để có tấm bằng cho oách v.v… thì còn một lí do nữa cũng khá legit là hắn đã “nghiện” rồi.

Đương nhiên còn lí do nữa quan trọng hơn là sự chây ì trong tư duy, không muốn get out of the comfort zone để start something new. Nhưng đó lại là chuyện khác…


Tuy nhiên nhiều tri thức hàn lâm quá cũng không hẳn là hay.

Cách đây không lâu, tôi từng có ý định đi học hoài không nghỉ. Chỉ cần tìm được chừng… 15 học bổng Cao học, sau khi học xong cả 15 khoá thì cũng đã ngoài 50 tuổi. Đến lúc đó sẽ ở nhà viết sách, cuộc đời có thể kết thúc một cách an nhàn và thú vị. Đương nhiên 15 khoá cao học có thể về bất cứ lĩnh vực nào, từ CS, thống kê, kinh tế học, tâm lí học, nghệ thuật, kiến trúc, âm nhạc, triết học v.v… Tất cả đều thú vị như nhau và đều có thể mang lại những niềm phấn khích khó lường trước được.

Tất nhiên ý tưởng có phần trào phúng này khá là phi thực tế, không phải chỉ vì độ khó của việc tìm được 15 học bổng Cao học liên tục, trong 30 năm, mà còn vì những kiến thức thu thập được, sau 30 năm, chưa chắc đã làm được gì đáng kể. Đến khi 50 tuổi ở nhà viết sách mà không ai đọc, thì thật có tội lớn với tổ tông.

Nói như một anh nhà văn nào đó, bao nhiêu tấn gỗ mới làm được một tấn giấy, nên những anh viết sách mà in ra chỉ dùng để gói bánh mì thì tội ác cũng không thua gì lâm tặc.

Cố nhiên sẽ tốt hơn nếu, trong 30 năm tới, làm được chuyện gì có ý nghĩa, chứ không phải trở thành ác hơn cả lâm tặc 😉

Anna Karenina principle

Mở đầu tiểu thuyết Anna Karenina, Lev Tolstoy viết:

Mọi gia đình hạnh phúc đều giống nhau, nhưng mỗi gia đình bất hạnh lại khổ sở theo cách riêng.

Nghe lần đầu thì có vẻ rất giản dị, nhất là khi lại đặt trong tiểu thuyết của Tolstoy, nhưng có lúc ngồi nghĩ lại mới thấy hàm ý sâu xa của nó.

Chẳng thế mà câu này đã được viết lại theo đủ kiểu khác nhau, chẳng hạn:

Good UX are all alike; every bad UX is bad in its own way

cho user experience design, hay là cho chính phủ:

Effective public agencies are all alike; every ineffective agency is ineffective in its own way

vốn được thuổng từ bài viết này.

Và đương nhiên không thể thiếu các nhà khoa học, với công việc “bếp núc” lo toan hàng ngày như là funding, publications, new idea…

Well… successes are all alike; every failure fails in its own way…