Graph Processing with PUMA
CC Attribution 2.0 Belgium:
You are free to use, adapt and copy, distribute and transmit the work or content in adapted or unchanged form for any legal purpose as long as the work is attributed to the author in the manner specified by the author or licensor.
Eyerman, Stijn
Heirman, Wim
Hur, Ibrahim
Fryman, Joshua B.
Large scale graph analytics is essential to analyze relationships in big data sets. Thereto, the DARPA HIVE program targets a leap in power efficient graph analytics. In response to this program, Intel proposes the Programmable Unified Memory Architecture (PUMA). Based on graph workload analysis insights, PUMA consists of many multi-threaded cores, fine-grained memory and network accesses, a globally shared address space and powerful offload engines. In this talk, we will describe the PUMA architecture, both in terms of hardware and the software ecosystem. We will provide initial simulation based performance estimations, showing that for graph analysis applications, a PUMA node will outperform a conventional compute node by one to two orders of magnitude. Additionally, PUMA will continue to scale across multiple nodes, which is a challenge in conventional multinode setups.
 So let's continue. I'm very happy to announce Stain who is working with Intel and he's talking about programmable unified memory architecture, Puma and how you do the same. Okay, thank you. I'm afraid there's going to be another hardware talk, but I keep it simple and hope that you appreciate the fact that the hardware is also evolving and that we're looking at more efficient processors for graph processing. So, as you all know, graph processing is getting bigger and bigger and graphs are getting bigger and bigger and we want to process more data. So we set ourselves a, so we found that that we need to increase the efficiency of graph processing versus the existing architecture such as CPUs and GPUs. So to that, we propose the programmable unified memory architecture abbreviated as Puma. And in this talk, I want to explain to you why graph processing is actually challenging on the existing architectures. What makes Puma fit for graph processing? So high level details about Puma and how it performs. And after this presentation, you probably get a question, can we buy Puma? Unfortunately not yet because it's still under development. Okay, as you all know, Intel is a market leader of high performance processors. And in these processors, we've implemented a lot of things for regular applications that work very well such as branch predictions, branches, and more, and regular applications are very predictable. So we use that to predict branches ahead such that we can flow the instructions more in a continuous way. We have cashiers that assumes that if you access some data, you will access it again in the near future or its neighboring data. We have vector operations that perform the same operation of neighboring data. And all that works good for regular applications, but graph applications as the previous speaker also explained are not that nice for these architectures. For example, many of the graph applications have many branches that are data dependent. So the actual outcome of the branch depends on the data that is in the graph and which is of course not predictable. So branch predictors don't work well. Data is also accessed in a scattered way. So that was also introduced by the previous speaker. So you access the neighbors and the neighbors are not the next notes in your list of notes. They are scattered all over the place. So cashiers don't work well because you don't use the neighboring data or don't reuse the same data and the same for vector operations. So we have, we see very low performance on regular CPUs for graph applications. Many people have proposed to use GPUs. They are actually better in general because of higher bandwidth and more threats, but they actually suffer from the same problems. If branches diverge, so go to another direction, then you cannot, the parallelism cannot be fully exploited. Scattered memory accesses prevents to use memory-colescing, meaning that all of the efficient things you cannot use in GPUs too. And we also saw before in previous presentations, there is a problem of memory capacity and scaling out. So what are potential solutions? There have been proposals of graph accelerators, so that specific chips made for graph applications that have some functionality. For example, that implement sparse linear algebra algorithms or vertex-centric algorithms. The problem there is that you're fixed with that functionality. So if your application or your algorithm works best for within the sparse linear algebra, but your accelerator is a vertex-centric operation accelerator, then you need to transfer your application and potentially, and you also need a host, so a CPU that controls this accelerator, and there is the data transfer between both. Another solution is to have a general instruction set processor like the normal CPUs, but that's been optimized for graph applications, which is then more flexible because you have an instruction set, you can implement other algorithms too, it self-contained, you don't need a host per se, and that's actually what our approach was in Puma. Okay, I've talked about the challenges that graph applications pose. So how did we solve that in Puma? Most of the graph applications are very memory bound, so most of the time, if you have a very fast core, a Xeon core, for example, it's just stuck by the slow memory, it's waiting forever, so you cannot use all of its speed. So instead, in Puma, we have much lighter cores, much slower cores, but we have many of them. So they still wait for memory, but because we have many of them, the total throughput is higher. As I said before, caching was a problem. So the problem is that if you load data, you only need that one element that you load, not the full cache length. So in a conventional architecture, you load the full cache length from memory through the memory bus into the cache and then to the core, but as you see, only the blue points are used, it's very inefficient use of the cache capacity and of the memory bandwidth. So that means you waste a lot of things, a lot of potential. For Puma, we have a lot of cores, but we also optimize the memory accesses such that you can access only a single element. We bypass caches because they're not efficient to get more chip area for cores and other stuff and get more fluid flow of memory operations. Another thing is the size of the graph. So if you have a very large graph, you need to partition it and put it into multiple nodes, multiple compute nodes, multiple servers. But then when the graph algorithm wants to access data on another node, it needs to go to the whole communications stack, which takes a lot of time and unfortunately, graph algorithms are not very predictable in their locality. So it often happens, occurs that we need to go off node giving a large performance penalty. So for Puma, we have this hardware distributed shared memory. You don't need to share memory across the whole system. You don't need to think about communication. The network is high bandwidth low latency just to reduce the latency or the performance impact of remote accesses. Another thing that we saw that is that there are very a lot of common patterns in graph applications and we designed some offload engines that efficiently execute these patterns. For example, atomics are very much used in graph algorithms, but for a core that's a very intensive operation. So you have to log data, you have to load the data, update it and write it back and unlock the data. So the core is often stuck a long time performing this atomic. So in Puma, we have this offload engine that performs the atomic that relieves the core from performing this atomic. So just the core issues and atomic instruction, but leaves the execution over to the offload engine and the core can continue executing other instructions in the background. So the operation is done in the background and the offload engine looks where the data is located and performs the update locally. Similarly, a gather operations, for example, if you want to gather the some characteristics of the neighbors of a vertex. The normal operation is that you load the index of the first neighbor, then you load the data of the neighbor and store it somewhere. So that's a very intensive process for the core. So we have this DMA gather offload engine. So the core again just issues this DMA gather instruction and then continues executing. And in the background, the offload engine performs the necessary memory accesses without actually needing to move the data, all the data to the core itself. Other operations are memcopy, barriers, skews and so forth. So going to into a little bit more architectural detail of a single Puma core. So that's a schematic overview of a single Puma core. It consists of multiple pipelines. So each of these are pipelines. Each pipeline supports multiple threats. Why, like the previous presenters says, said, most of the time we are waiting for memory operations. If we are meeting for memory operations, we just switch to another threat. If this one is also waiting, switch to yet another type and so on, just to hide all of this memory latency. We have limit is cash is you have an instruction case of data cash, which are very small. It's for a very local data such as the stack of your threat. The instructions executed by discourse are a novel instruction set that we designed. It's based on a reduced instruction sets, so simple instructions. And we added specific instructions that are you can be used by graph operations search as a single instruction in direct load. Because we have limited caching, we don't want to go to main memory all of the time for data that's been been consumed and produced locally. So we have a manually accessible scratch pad so the programmer can decide whether to cash its data to use a scratch pad or to go to main memory. It's part of the global and their space. So other course can also access the scratch pad of this core. I talked about offload engines, so they perform these operations in the background. We have a memory controller that's been optimized for these small accesses, a bite accesses, and we have a network interface to connect to other course. Also, of course, using this eight by packets because most of the data is trans is used in the small granular granularities. Okay, the full format system as we envision it is is hierarchically built. You have multiple of these scores it formatile multiples of these styles for my note multiples of the these notes for my system. And that means that a since you have already that many threats on a chord, you have that many cores on the towel and so on, that the full system can easily consist of millions of hardware context for threats. Again, the global address space and the memory is shared across the full system. So you can access any data from any point in the system. Of course, this requires a very high bandwidth low latency network. So we use hyper X network topology. This is the textbook Chris representation of this. So you have a hierarchical design where within each level, our everything is fully connected. And then on the next level, they are connections between the levels. Furthermore, we plan to have optical connections between the 1000 between notes again to increase than to the latency. More interesting for you, maybe is how do we program this beast. That's the work in progress. So we're also working and had a software infrastructure for this architecture. Initially, where we did our first experiments with is a simple as PMB based parallelism using see and we use intrinsics, special intrinsics for the specific instructions and for building a compiler. In the meantime, there has been increasing support for C plus plus p threats open MP and some tasking. And we're also looking at implementing common graph libraries, other program languages and a Python front end. Okay. Now, importantly, does pull map fulfill its premises namely that it's more efficient to to do graph analysis on it. Of course, the chip is not available yet. Neither is so. So we are also working at FPGA model, but that's not ready yet. So basically results that I will show are based on simulation where you take a Puma binary. You have a functional simulator that decodes the instructions of the binary that performs the actual simulates the operations and I have the timing simulation that gives us that models all of the hardware structures such as the course the memory scratch pad and so on. And that gives us a performance number and also interesting for developers a profile of how the execution looks like where course or idle that's the pink part or used or waiting for memory. That's the light blue part such that the developers can optimize it find the bottlenecks and opt in optimize their application. And then we use an analytical model which I won't go into detail because simulation is a very intensive process so we can simulate up to a few tiles, but after that it becomes quickly infeasible and then therefore we use this analytical model, which we then validate using simulation on a smaller course. A whole bunch of kernels graph kernels and applications. We run them on a high end Intel Xeon server with four sockets. We optimize them if needed, and we also also ported and optimized these applications for Puma. The initial estimates show that this high end Xeon server with four sockets will approximately consumes the same power as a Puma note will consume in the future. So, comparing their performances also a energy efficiency comparison. We have some multi notes on Xeon but that didn't work well because you use it you have this communication overhead that results that the result was that we saw no speed up for most applications or even slowdowns. We projected to 16 Puma notes and as I will show shortly this skills much better. There is an overview of some of the applications and performance results so it shows the speed up of a single Puma note versus a high end Xeon server. And you see that there is a there is always speed up there is a but there is a large range so it goes from two times to 200 more than 200 times faster than Xeon. Some applications are more compute intensive so they do more compute and of course there the Xeon can use all of its resources to efficiently do that. On the other hand, if it's purely memory bandwidth bounce such as random walks, then we see a very huge performance increase and the 60 note projections also show that it scales much better than Xeon does. It was basically get so I showed you that Puma is a programmable instruction set processor for graph applications. It contains many features which I discussed and we show that it's through simulation and modeling that it's one to two orders of magnitude faster than a equal power Xeon and its skills well to multi note. And it's still in the development of course. Okay, that's it. Thank you very much. Very interesting perspective on graph processing. Questions? Do you see that this will be sitting, you think that this will be affordable as a rock station or would you say no, this is a cloud installation that is somewhere in the server center or where do you see? So the question is, is whether this is a is a workstation PC or desktop based thing or a no, it will be more in a data center or big supercomputer setup. Is it possible kind of going on to what he asked to have these courses like coprocessing course like you have like a few big normal course and a few Puma course with that. So that's if we plan to have some, let's say it host nodes or yeah, we're still working on that. So there isn't there is an option to have potentially x86 nodes that do more of the other stuff that this is not efficient for but that's still under development. So it's not in the same way as on zon but I'm afraid I cannot go into detail. So how it will work. You mentioned sort of the shared memory architecture and there's different sort of processing units. Does the does it matter where in memory is the location of the values needed for certain cores. So if they're closed by, they'll be a faster access or it doesn't matter since it's an all to all connection. But what's the penalty of data being further away in memory to the core that. Okay, so the question is, is further is data that's further in memory. Will it be slower to access it. Yes, of course, because it's a very large system it's distributed across the system will be distributed because multiple nodes multiple racks. So there will be a larger penalty but because of this all of this memory latency hiding techniques and these offload engines that perform it very efficiently. You won't see as much as you see in conventional multi nodes setup. Yeah, that's it. Sorry. Maybe take more questions. So thanks again.
 So let's continue.  I'm very happy to announce Stain who is working with Intel and he's talking about programmable  unified memory architecture, Puma and how you do the same.  Okay, thank you.  I'm afraid there's going to be another hardware talk, but I keep it simple and hope that you appreciate the fact that the hardware is also  evolving and that we're looking at more efficient processors for graph processing.  So, as you all know, graph processing is getting bigger and bigger and graphs are getting bigger and bigger and we want to process more data.  So we set ourselves a, so we found that that we need to increase the efficiency of graph processing versus the existing architecture such as CPUs and GPUs.  So to that, we propose the programmable unified memory architecture abbreviated as Puma.  And in this talk, I want to explain to you why graph processing is actually challenging on the existing architectures.  What makes Puma fit for graph processing?  So high level details about Puma and how it performs.  And after this presentation, you probably get a question, can we buy Puma?  Unfortunately not yet because it's still under development.  Okay, as you all know, Intel is a market leader of high performance processors.  And in these processors, we've implemented a lot of things for regular applications that work very well such as branch predictions, branches, and more, and regular applications are very predictable.  So we use that to predict branches ahead such that we can flow the instructions more in a continuous way.  We have cashiers that assumes that if you access some data, you will access it again in the near future or its neighboring data.  We have vector operations that perform the same operation of neighboring data.  And all that works good for regular applications, but graph applications as the previous speaker also explained are not that nice for these architectures.  For example, many of the graph applications have many branches that are data dependent.  So the actual outcome of the branch depends on the data that is in the graph and which is of course not predictable.  So branch predictors don't work well.  Data is also accessed in a scattered way.  So that was also introduced by the previous speaker.  So you access the neighbors and the neighbors are not the next notes in your list of notes.  They are scattered all over the place.  So cashiers don't work well because you don't use the neighboring data or don't reuse the same data and the same for vector operations.  So we have, we see very low performance on regular CPUs for graph applications.  Many people have proposed to use GPUs.  They are actually better in general because of higher bandwidth and more threats, but they actually suffer from the same problems.  If branches diverge, so go to another direction, then you cannot, the parallelism cannot be fully exploited.  Scattered memory accesses prevents to use memory-colescing, meaning that all of the efficient things you cannot use in GPUs too.  And we also saw before in previous presentations, there is a problem of memory capacity and scaling out.  So what are potential solutions?  There have been proposals of graph accelerators, so that specific chips made for graph applications that have some functionality.  For example, that implement sparse linear algebra algorithms or vertex-centric algorithms.  The problem there is that you're fixed with that functionality.  So if your application or your algorithm works best for within the sparse linear algebra, but your accelerator is a vertex-centric operation accelerator,  then you need to transfer your application and potentially, and you also need a host, so a CPU that controls this accelerator,  and there is the data transfer between both.  Another solution is to have a general instruction set processor like the normal CPUs, but that's been optimized for graph applications,  which is then more flexible because you have an instruction set, you can implement other algorithms too, it self-contained, you don't need a host per se,  and that's actually what our approach was in Puma.  Okay, I've talked about the challenges that graph applications pose.  So how did we solve that in Puma?  Most of the graph applications are very memory bound, so most of the time, if you have a very fast core, a Xeon core, for example,  it's just stuck by the slow memory, it's waiting forever, so you cannot use all of its speed.  So instead, in Puma, we have much lighter cores, much slower cores, but we have many of them.  So they still wait for memory, but because we have many of them, the total throughput is higher.  As I said before, caching was a problem.  So the problem is that if you load data, you only need that one element that you load, not the full cache length.  So in a conventional architecture, you load the full cache length from memory through the memory bus into the cache and then to the core,  but as you see, only the blue points are used, it's very inefficient use of the cache capacity and of the memory bandwidth.  So that means you waste a lot of things, a lot of potential.  For Puma, we have a lot of cores, but we also optimize the memory accesses such that you can access only a single element.  We bypass caches because they're not efficient to get more chip area for cores and other stuff and get more fluid flow of memory operations.  Another thing is the size of the graph.  So if you have a very large graph, you need to partition it and put it into multiple nodes, multiple compute nodes, multiple servers.  But then when the graph algorithm wants to access data on another node, it needs to go to the whole communications stack,  which takes a lot of time and unfortunately, graph algorithms are not very predictable in their locality.  So it often happens, occurs that we need to go off node giving a large performance penalty.  So for Puma, we have this hardware distributed shared memory.  You don't need to share memory across the whole system.  You don't need to think about communication.  The network is high bandwidth low latency just to reduce the latency or the performance impact of remote accesses.  Another thing that we saw that is that there are very a lot of common patterns in graph applications and we designed some offload engines that efficiently execute these patterns.  For example, atomics are very much used in graph algorithms, but for a core that's a very intensive operation.  So you have to log data, you have to load the data, update it and write it back and unlock the data.  So the core is often stuck a long time performing this atomic.  So in Puma, we have this offload engine that performs the atomic that relieves the core from performing this atomic.  So just the core issues and atomic instruction, but leaves the execution over to the offload engine and the core can continue executing other instructions in the background.  So the operation is done in the background and the offload engine looks where the data is located and performs the update locally.  Similarly, a gather operations, for example, if you want to gather the some characteristics of the neighbors of a vertex.  The normal operation is that you load the index of the first neighbor, then you load the data of the neighbor and store it somewhere.  So that's a very intensive process for the core.  So we have this DMA gather offload engine. So the core again just issues this DMA gather instruction and then continues executing.  And in the background, the offload engine performs the necessary memory accesses without actually needing to move the data, all the data to the core itself.  Other operations are memcopy, barriers, skews and so forth.  So going to into a little bit more architectural detail of a single Puma core.  So that's a schematic overview of a single Puma core.  It consists of multiple pipelines. So each of these are pipelines.  Each pipeline supports multiple threats. Why, like the previous presenters says, said, most of the time we are waiting for memory operations.  If we are meeting for memory operations, we just switch to another threat. If this one is also waiting, switch to yet another type and so on, just to hide all of this memory latency.  We have limit is cash is you have an instruction case of data cash, which are very small.  It's for a very local data such as the stack of your threat.  The instructions executed by discourse are a novel instruction set that we designed.  It's based on a reduced instruction sets, so simple instructions.  And we added specific instructions that are you can be used by graph operations search as a single instruction in direct load.  Because we have limited caching, we don't want to go to main memory all of the time for data that's been been consumed and produced locally.  So we have a manually accessible scratch pad so the programmer can decide whether to cash its data to use a scratch pad or to go to main memory.  It's part of the global and their space.  So other course can also access the scratch pad of this core.  I talked about offload engines, so they perform these operations in the background.  We have a memory controller that's been optimized for these small accesses, a bite accesses, and we have a network interface to connect to other course.  Also, of course, using this eight by packets because most of the data is trans is used in the small granular granularities.  Okay, the full format system as we envision it is is hierarchically built.  You have multiple of these scores it formatile multiples of these styles for my note multiples of the these notes for my system.  And that means that a since you have already that many threats on a chord, you have that many cores on the towel and so on, that the full system can easily consist of millions of hardware context for threats.  Again, the global address space and the memory is shared across the full system.  So you can access any data from any point in the system.  Of course, this requires a very high bandwidth low latency network.  So we use hyper X network topology.  This is the textbook Chris representation of this.  So you have a hierarchical design where within each level, our everything is fully connected.  And then on the next level, they are connections between the levels.  Furthermore, we plan to have optical connections between the 1000 between notes again to increase than to the latency.  More interesting for you, maybe is how do we program this beast.  That's the work in progress.  So we're also working and had a software infrastructure for this architecture.  Initially, where we did our first experiments with is a simple as PMB based parallelism using see and we use intrinsics, special intrinsics for the specific instructions and for building a compiler.  In the meantime, there has been increasing support for C plus plus p threats open MP and some tasking.  And we're also looking at implementing common graph libraries, other program languages and a Python front end.  Okay.  Now, importantly, does pull map fulfill its premises namely that it's more efficient to to do graph analysis on it.  Of course, the chip is not available yet.  Neither is so.  So we are also working at FPGA model, but that's not ready yet.  So basically results that I will show are based on simulation where you take a Puma binary.  You have a functional simulator that decodes the instructions of the binary that performs the actual simulates the operations and I have the timing simulation that gives us that models all of the hardware structures such as the course the memory scratch pad and so on.  And that gives us a performance number and also interesting for developers a profile of how the execution looks like where course or idle that's the pink part or used or waiting for memory.  That's the light blue part such that the developers can optimize it find the bottlenecks and opt in optimize their application.  And then we use an analytical model which I won't go into detail because simulation is a very intensive process so we can simulate up to a few tiles, but after that it becomes quickly infeasible and then therefore we use this analytical model, which we then validate using  simulation on a smaller course.  A whole bunch of kernels graph kernels and applications. We run them on a high end Intel Xeon server with four sockets.  We optimize them if needed, and we also also ported and optimized these applications for Puma.  The initial estimates show that this high end Xeon server with four sockets will approximately consumes the same power as a Puma note will consume in the future.  So, comparing their performances also a energy efficiency comparison.  We have some multi notes on Xeon but that didn't work well because you use it you have this communication overhead that results that the result was that we saw no speed up for most applications or even slowdowns.  We projected to 16 Puma notes and as I will show shortly this skills much better.  There is an overview of some of the applications and performance results so it shows the speed up of a single Puma note versus a high end Xeon server.  And you see that there is a there is always speed up there is a but there is a large range so it goes from two times to 200 more than 200 times faster than Xeon.  Some applications are more compute intensive so they do more compute and of course there the Xeon can use all of its resources to efficiently do that.  On the other hand, if it's purely memory bandwidth bounce such as random walks, then we see a very huge performance increase and the 60 note projections also show that it scales much better than Xeon does.  It was basically get so I showed you that Puma is a programmable instruction set processor for graph applications.  It contains many features which I discussed and we show that it's through simulation and modeling that it's one to two orders of magnitude faster than a equal power Xeon and its skills well to multi note.  And it's still in the development of course.  Okay, that's it.  Thank you very much. Very interesting perspective on graph processing.  Questions?  Do you see that this will be sitting, you think that this will be affordable as a rock station or would you say no, this is a cloud installation that is somewhere in the server center or where do you see?  So the question is, is whether this is a is a workstation PC or desktop based thing or a no, it will be more in a data center or big supercomputer setup.  Is it possible kind of going on to what he asked to have these courses like coprocessing course like you have like a few big normal course and a few Puma course with that.  So that's if we plan to have some, let's say it host nodes or yeah, we're still working on that. So there isn't there is an option to have potentially x86 nodes that do more of the other stuff that this is not efficient for but that's still under development.  So it's not in the same way as on zon but I'm afraid I cannot go into detail. So how it will work.  You mentioned sort of the shared memory architecture and there's different sort of processing units. Does the does it matter where in memory is the location of the values needed for certain cores.  So if they're closed by, they'll be a faster access or it doesn't matter since it's an all to all connection. But what's the penalty of data being further away in memory to the core that.  Okay, so the question is, is further is data that's further in memory. Will it be slower to access it. Yes, of course, because it's a very large system it's distributed across the system will be distributed because multiple nodes multiple racks.  So there will be a larger penalty but because of this all of this memory latency hiding techniques and these offload engines that perform it very efficiently. You won't see as much as you see in conventional multi nodes setup.  Yeah, that's it. Sorry. Maybe take more questions. So thanks again.
graph_puma_0_179.png graph_puma_180_911.png graph_puma_912_1463.png graph_puma_1464_1679.png graph_puma_1680_1883.png graph_puma_1884_1967.png graph_puma_1968_2039.png graph_puma_2040_2111.png graph_puma_2112_2315.png graph_puma_2316_7487.png graph_puma_7488_8159.png graph_puma_8160_8459.png graph_puma_8460_10319.png graph_puma_10320_11255.png graph_puma_11256_12047.png graph_puma_12048_13943.png graph_puma_13944_16979.png graph_puma_16980_18767.png graph_puma_18768_20075.png graph_puma_20076_20627.png graph_puma_20628_22403.png graph_puma_22404_22751.png graph_puma_22752_24023.png graph_puma_24024_25223.png graph_puma_25224_25415.png graph_puma_25416_25499.png graph_puma_25500_25763.png graph_puma_25764_30503.png graph_puma_30504_30587.png graph_puma_30588_30703.png