CSC/ECE 506 Spring 2013/2b ks - Revision history

Skey: /* Overview */

2013-02-10T23:59:39Z

Overview

← Older revision		Revision as of 23:59, 10 February 2013
Line 43:		Line 43:
	=GPGPU Data Parallelism=		=GPGPU Data Parallelism=
	==Overview==		==Overview==
	With the ~~evolutions in GPU’s, especially in regards to their~~ floating calculations, and ~~also~~ the ~~software progressions made by~~ Nvidia and Apple ~~with their API’s to interface with this different type of hardware~~, ~~made~~ it ~~very attractive~~ to developers to try to take advantage. What all of these advances meant to the development community is that data parallelism had proven very powerful in the graphics rendering arena and could be leveraged for other types of application processing. From a high level, the algorithmic concept that these API’s take advantage of is data is arranged in data structures that can be executed in parallel. These data structures are aligned to an index space. How this index space is determined is based on the data and how much information needs to be shared. Ideally the indexes will be aligned so that the data in a particular index interacts with data in other indexes as minimally as possible. At this point a sequence of operations is applied across these indexes. During occasions where data elements do need to be shared, performance can remain relatively intact based on shift operations and masking techniques[http://parlab.eecs.berkeley.edu/wiki/_media/patterns/data_parallel.pdf], as long as they are kept beneath a certain rate of occurrence. This data processing model lyes at the core of GPGPU and in conjunction with the SIMD execution model that contains its own specialized data structures and alignment operations combine to create a type of framework that APIs such as CUDA and OpenCL leverage to get peak performance out of the software applications that interface with them.
			With the introduction of floating point calculations and APIs from the likes of Nvidia and Apple, it became more appealing to developers to try and take advantage of the parallelism GPUs provided. What all of these advances meant to the development community is that data parallelism had proven very powerful in the graphics rendering arena and could be leveraged for other types of application processing. From a high level, the algorithmic concept that these API’s take advantage of is data is arranged in data structures that can be executed in parallel. These data structures are aligned to an index space. How this index space is determined is based on the data and how much information needs to be shared. Ideally the indexes will be aligned so that the data in a particular index interacts with data in other indexes as minimally as possible. At this point a sequence of operations is applied across these indexes. During occasions where data elements do need to be shared, performance can remain relatively intact based on shift operations and masking techniques[http://parlab.eecs.berkeley.edu/wiki/_media/patterns/data_parallel.pdf], as long as they are kept beneath a certain rate of occurrence. This data processing model lyes at the core of GPGPU and in conjunction with the SIMD execution model that contains its own specialized data structures and alignment operations combine to create a type of framework that APIs such as CUDA and OpenCL leverage to get peak performance out of the software applications that interface with them.

	To give a bit more background on data parallelism we will discuss in a bit more detail how the process is achieved and how it has evolved. The first most basic scenario we will talk about is Oversubscription. If we think of each of our data structures that we have created along an index as a worker, and this collection of workers are all trying to complete a job, then In this type of parallelism, resources are allocated based on which worker has the most work to do. So all of the workers have the same amount of resources even though it is highly likely that very few of the workers actually need that amount of resources[https://wiki.aalto.fi/download/attachments/70779066/T-106.5840_2012_Halme.pdf?version=1&modificationDate=1357205607000]. It is a rather wasteful model as programmers will typically allocate many more sources than they will actually use, but it helps illustrate the concept of how parallelism works. Moving from that example to Serialization helps a bit. In the model this workers run in parallel but individually execute sequentially. Now you are only allocated as many resources as each worker needs. We solved one challenge with Oversubscription but we still have another, and that is that each worker can have a very unbalanced workload compared to the other workers. We have no way of knowing if all of the workers are being utilized fully to get maximum efficiency. This is where the concept of flattening comes in. Here, before the workload is distributed among the workers it is organized in evenly weighted vectors. This is why it is also referred to as vectorized parallelism[http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.118.9152&rep=rep1&type=pdf]. Here the workers do the same job as the previous models, but complication is introduced in accurately flattening the data and also extensive logging operations to keep track of how the work has been separated. Finally we have Dynamic Parallelism where we introduce a concept called work stealing. In this model, when a worker becomes overburdened they can divide out that work and spin up a new job. At that point another worker, perhaps one that is idle can take over that job thus relieving the initial worker from that burden. This dynamic model brings a lot of flexibility and elasticity to parallelism. The tradeoff to this is greater runtime analysis and logic supplied by the developer[http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.118.9152&rep=rep1&type=pdf].		To give a bit more background on data parallelism we will discuss in a bit more detail how the process is achieved and how it has evolved. The first most basic scenario we will talk about is Oversubscription. If we think of each of our data structures that we have created along an index as a worker, and this collection of workers are all trying to complete a job, then In this type of parallelism, resources are allocated based on which worker has the most work to do. So all of the workers have the same amount of resources even though it is highly likely that very few of the workers actually need that amount of resources[https://wiki.aalto.fi/download/attachments/70779066/T-106.5840_2012_Halme.pdf?version=1&modificationDate=1357205607000]. It is a rather wasteful model as programmers will typically allocate many more sources than they will actually use, but it helps illustrate the concept of how parallelism works. Moving from that example to Serialization helps a bit. In the model this workers run in parallel but individually execute sequentially. Now you are only allocated as many resources as each worker needs. We solved one challenge with Oversubscription but we still have another, and that is that each worker can have a very unbalanced workload compared to the other workers. We have no way of knowing if all of the workers are being utilized fully to get maximum efficiency. This is where the concept of flattening comes in. Here, before the workload is distributed among the workers it is organized in evenly weighted vectors. This is why it is also referred to as vectorized parallelism[http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.118.9152&rep=rep1&type=pdf]. Here the workers do the same job as the previous models, but complication is introduced in accurately flattening the data and also extensive logging operations to keep track of how the work has been separated. Finally we have Dynamic Parallelism where we introduce a concept called work stealing. In this model, when a worker becomes overburdened they can divide out that work and spin up a new job. At that point another worker, perhaps one that is idle can take over that job thus relieving the initial worker from that burden. This dynamic model brings a lot of flexibility and elasticity to parallelism. The tradeoff to this is greater runtime analysis and logic supplied by the developer[http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.118.9152&rep=rep1&type=pdf].

Kcelrod2: /* Overview */

2013-02-10T23:58:19Z

Overview

← Older revision		Revision as of 23:58, 10 February 2013
Line 45:		Line 45:
	With the evolutions in GPU’s, especially in regards to their floating calculations, and also the software progressions made by Nvidia and Apple with their API’s to interface with this different type of hardware, made it very attractive to developers to try to take advantage. What all of these advances meant to the development community is that data parallelism had proven very powerful in the graphics rendering arena and could be leveraged for other types of application processing. From a high level, the algorithmic concept that these API’s take advantage of is data is arranged in data structures that can be executed in parallel. These data structures are aligned to an index space. How this index space is determined is based on the data and how much information needs to be shared. Ideally the indexes will be aligned so that the data in a particular index interacts with data in other indexes as minimally as possible. At this point a sequence of operations is applied across these indexes. During occasions where data elements do need to be shared, performance can remain relatively intact based on shift operations and masking techniques[http://parlab.eecs.berkeley.edu/wiki/_media/patterns/data_parallel.pdf], as long as they are kept beneath a certain rate of occurrence. This data processing model lyes at the core of GPGPU and in conjunction with the SIMD execution model that contains its own specialized data structures and alignment operations combine to create a type of framework that APIs such as CUDA and OpenCL leverage to get peak performance out of the software applications that interface with them.		With the evolutions in GPU’s, especially in regards to their floating calculations, and also the software progressions made by Nvidia and Apple with their API’s to interface with this different type of hardware, made it very attractive to developers to try to take advantage. What all of these advances meant to the development community is that data parallelism had proven very powerful in the graphics rendering arena and could be leveraged for other types of application processing. From a high level, the algorithmic concept that these API’s take advantage of is data is arranged in data structures that can be executed in parallel. These data structures are aligned to an index space. How this index space is determined is based on the data and how much information needs to be shared. Ideally the indexes will be aligned so that the data in a particular index interacts with data in other indexes as minimally as possible. At this point a sequence of operations is applied across these indexes. During occasions where data elements do need to be shared, performance can remain relatively intact based on shift operations and masking techniques[http://parlab.eecs.berkeley.edu/wiki/_media/patterns/data_parallel.pdf], as long as they are kept beneath a certain rate of occurrence. This data processing model lyes at the core of GPGPU and in conjunction with the SIMD execution model that contains its own specialized data structures and alignment operations combine to create a type of framework that APIs such as CUDA and OpenCL leverage to get peak performance out of the software applications that interface with them.

	To give a bit more background on data parallelism we will discuss in a bit more detail how the process is achieved and how it has evolved. The first most basic scenario we will talk about is Oversubscription. If we think of each of our data structures that we have created along an index as a worker, and this collection of workers are all trying to complete a job, then In this type of parallelism, resources are allocated based on which worker has the most work to do. So all of the workers have the same amount of resources even though it is highly likely that very few of the workers actually need that amount of resources[https://wiki.aalto.fi/download/attachments/70779066/T-106.5840_2012_Halme.pdf?version=1&modificationDate=1357205607000]. It is a rather wasteful model as programmers will typically allocate many more sources than they will actually use, but it helps illustrate the concept of how parallelism works. Moving from that example to Serialization helps a bit. In the model this workers run in parallel but individually execute sequentially. Now you are only allocated as many resources as each worker needs. We solved one challenge with Oversubscription but we still have another, and that is that each worker can have a very unbalanced workload compared to the other workers. We have no way of knowing if all of the workers are being utilized fully to get maximum efficiency. This is where the concept of flattening comes in. Here before the workload is distributed among the workers it is organized in evenly weighted vectors. This is why it is also referred to as vectorized parallelism[http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.118.9152&rep=rep1&type=pdf]. Here the workers do the same job as the previous models, but complication is introduced in accurately flattening the data and also extensive logging operations to keep track of how the work has been separated. Finally we have Dynamic Parallelism where we introduce a concept called work stealing. In this model, when a worker becomes overburdened they can divide out that work and spin up a new job. At that point another worker, perhaps one that is idle can take over that job thus relieving the initial worker from that burden. This dynamic model brings a lot of flexibility and elasticity to parallelism. The tradeoff to this is greater runtime analysis and logic supplied by the developer[http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.118.9152&rep=rep1&type=pdf].		To give a bit more background on data parallelism we will discuss in a bit more detail how the process is achieved and how it has evolved. The first most basic scenario we will talk about is Oversubscription. If we think of each of our data structures that we have created along an index as a worker, and this collection of workers are all trying to complete a job, then In this type of parallelism, resources are allocated based on which worker has the most work to do. So all of the workers have the same amount of resources even though it is highly likely that very few of the workers actually need that amount of resources[https://wiki.aalto.fi/download/attachments/70779066/T-106.5840_2012_Halme.pdf?version=1&modificationDate=1357205607000]. It is a rather wasteful model as programmers will typically allocate many more sources than they will actually use, but it helps illustrate the concept of how parallelism works. Moving from that example to Serialization helps a bit. In the model this workers run in parallel but individually execute sequentially. Now you are only allocated as many resources as each worker needs. We solved one challenge with Oversubscription but we still have another, and that is that each worker can have a very unbalanced workload compared to the other workers. We have no way of knowing if all of the workers are being utilized fully to get maximum efficiency. This is where the concept of flattening comes in. Here, before the workload is distributed among the workers it is organized in evenly weighted vectors. This is why it is also referred to as vectorized parallelism[http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.118.9152&rep=rep1&type=pdf]. Here the workers do the same job as the previous models, but complication is introduced in accurately flattening the data and also extensive logging operations to keep track of how the work has been separated. Finally we have Dynamic Parallelism where we introduce a concept called work stealing. In this model, when a worker becomes overburdened they can divide out that work and spin up a new job. At that point another worker, perhaps one that is idle can take over that job thus relieving the initial worker from that burden. This dynamic model brings a lot of flexibility and elasticity to parallelism. The tradeoff to this is greater runtime analysis and logic supplied by the developer[http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.118.9152&rep=rep1&type=pdf].

	[[File:DataParallelism_DataStructures.png\|center\|frame\|265x562px\|Data Parallelism Data Structures as shown in Functional Programming for Nested Data Parallelism on GPUs [https://wiki.aalto.fi/download/attachments/70779066/T-106.5840_2012_Halme.pdf?version=1&modificationDate=1357205607000]]]		[[File:DataParallelism_DataStructures.png\|center\|frame\|265x562px\|Data Parallelism Data Structures as shown in Functional Programming for Nested Data Parallelism on GPUs [https://wiki.aalto.fi/download/attachments/70779066/T-106.5840_2012_Halme.pdf?version=1&modificationDate=1357205607000]]]

Kcelrod2: /* Overview */

2013-02-10T23:57:51Z

Overview

← Older revision		Revision as of 23:57, 10 February 2013
Line 45:		Line 45:
	With the evolutions in GPU’s, especially in regards to their floating calculations, and also the software progressions made by Nvidia and Apple with their API’s to interface with this different type of hardware, made it very attractive to developers to try to take advantage. What all of these advances meant to the development community is that data parallelism had proven very powerful in the graphics rendering arena and could be leveraged for other types of application processing. From a high level, the algorithmic concept that these API’s take advantage of is data is arranged in data structures that can be executed in parallel. These data structures are aligned to an index space. How this index space is determined is based on the data and how much information needs to be shared. Ideally the indexes will be aligned so that the data in a particular index interacts with data in other indexes as minimally as possible. At this point a sequence of operations is applied across these indexes. During occasions where data elements do need to be shared, performance can remain relatively intact based on shift operations and masking techniques[http://parlab.eecs.berkeley.edu/wiki/_media/patterns/data_parallel.pdf], as long as they are kept beneath a certain rate of occurrence. This data processing model lyes at the core of GPGPU and in conjunction with the SIMD execution model that contains its own specialized data structures and alignment operations combine to create a type of framework that APIs such as CUDA and OpenCL leverage to get peak performance out of the software applications that interface with them.		With the evolutions in GPU’s, especially in regards to their floating calculations, and also the software progressions made by Nvidia and Apple with their API’s to interface with this different type of hardware, made it very attractive to developers to try to take advantage. What all of these advances meant to the development community is that data parallelism had proven very powerful in the graphics rendering arena and could be leveraged for other types of application processing. From a high level, the algorithmic concept that these API’s take advantage of is data is arranged in data structures that can be executed in parallel. These data structures are aligned to an index space. How this index space is determined is based on the data and how much information needs to be shared. Ideally the indexes will be aligned so that the data in a particular index interacts with data in other indexes as minimally as possible. At this point a sequence of operations is applied across these indexes. During occasions where data elements do need to be shared, performance can remain relatively intact based on shift operations and masking techniques[http://parlab.eecs.berkeley.edu/wiki/_media/patterns/data_parallel.pdf], as long as they are kept beneath a certain rate of occurrence. This data processing model lyes at the core of GPGPU and in conjunction with the SIMD execution model that contains its own specialized data structures and alignment operations combine to create a type of framework that APIs such as CUDA and OpenCL leverage to get peak performance out of the software applications that interface with them.

	To give a bit more background on data parallelism we will discuss in a bit more detail how the process is achieved and how it has evolved. The first most basic scenario we will talk about is Oversubscription. If we think of each of our data structures that we have created along an index as a worker, and this collection of workers are all trying to complete a job, then In this type of parallelism, resources are allocated based on which worker has the most work to do. So all of the workers have the same amount of resources even though it is highly likely that very few of the workers actually need that amount of resources[https://wiki.aalto.fi/download/attachments/70779066/T-106.5840_2012_Halme.pdf?version=1&modificationDate=1357205607000]. It is a rather wasteful model as programmers will typically allocate many more sources than they will actually use but it helps illustrate the concept of how parallelism works. Moving from that example to Serialization helps a bit. In the model this workers run in parallel but individually execute sequentially. Now you are only allocated as many resources as each worker needs. We solved one challenge with Oversubscription but we still have another, and that is that each worker can have a very unbalanced workload compared to the other workers. We have no way of knowing if all of the workers are being utilized fully to get maximum efficiency. This is where the concept of flattening comes in. Here before the workload is distributed among the workers it is organized in evenly weighted vectors. This is why it is also referred to as vectorized parallelism[http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.118.9152&rep=rep1&type=pdf]. Here the workers do the same job as the previous models, but complication is introduced in accurately flattening the data and also extensive logging operations to keep track of how the work has been separated. Finally we have Dynamic Parallelism where we introduce a concept called work stealing. In this model, when a worker becomes overburdened they can divide out that work and spin up a new job. At that point another worker, perhaps one that is idle can take over that job thus relieving the initial worker from that burden. This dynamic model brings a lot of flexibility and elasticity to parallelism. The tradeoff to this is greater runtime analysis and logic supplied by the developer[http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.118.9152&rep=rep1&type=pdf].		To give a bit more background on data parallelism we will discuss in a bit more detail how the process is achieved and how it has evolved. The first most basic scenario we will talk about is Oversubscription. If we think of each of our data structures that we have created along an index as a worker, and this collection of workers are all trying to complete a job, then In this type of parallelism, resources are allocated based on which worker has the most work to do. So all of the workers have the same amount of resources even though it is highly likely that very few of the workers actually need that amount of resources[https://wiki.aalto.fi/download/attachments/70779066/T-106.5840_2012_Halme.pdf?version=1&modificationDate=1357205607000]. It is a rather wasteful model as programmers will typically allocate many more sources than they will actually use, but it helps illustrate the concept of how parallelism works. Moving from that example to Serialization helps a bit. In the model this workers run in parallel but individually execute sequentially. Now you are only allocated as many resources as each worker needs. We solved one challenge with Oversubscription but we still have another, and that is that each worker can have a very unbalanced workload compared to the other workers. We have no way of knowing if all of the workers are being utilized fully to get maximum efficiency. This is where the concept of flattening comes in. Here before the workload is distributed among the workers it is organized in evenly weighted vectors. This is why it is also referred to as vectorized parallelism[http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.118.9152&rep=rep1&type=pdf]. Here the workers do the same job as the previous models, but complication is introduced in accurately flattening the data and also extensive logging operations to keep track of how the work has been separated. Finally we have Dynamic Parallelism where we introduce a concept called work stealing. In this model, when a worker becomes overburdened they can divide out that work and spin up a new job. At that point another worker, perhaps one that is idle can take over that job thus relieving the initial worker from that burden. This dynamic model brings a lot of flexibility and elasticity to parallelism. The tradeoff to this is greater runtime analysis and logic supplied by the developer[http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.118.9152&rep=rep1&type=pdf].

	[[File:DataParallelism_DataStructures.png\|center\|frame\|265x562px\|Data Parallelism Data Structures as shown in Functional Programming for Nested Data Parallelism on GPUs [https://wiki.aalto.fi/download/attachments/70779066/T-106.5840_2012_Halme.pdf?version=1&modificationDate=1357205607000]]]		[[File:DataParallelism_DataStructures.png\|center\|frame\|265x562px\|Data Parallelism Data Structures as shown in Functional Programming for Nested Data Parallelism on GPUs [https://wiki.aalto.fi/download/attachments/70779066/T-106.5840_2012_Halme.pdf?version=1&modificationDate=1357205607000]]]

Kcelrod2: /* Overview */

2013-02-10T23:57:24Z

Overview

← Older revision		Revision as of 23:57, 10 February 2013
Line 45:		Line 45:
	With the evolutions in GPU’s, especially in regards to their floating calculations, and also the software progressions made by Nvidia and Apple with their API’s to interface with this different type of hardware, made it very attractive to developers to try to take advantage. What all of these advances meant to the development community is that data parallelism had proven very powerful in the graphics rendering arena and could be leveraged for other types of application processing. From a high level, the algorithmic concept that these API’s take advantage of is data is arranged in data structures that can be executed in parallel. These data structures are aligned to an index space. How this index space is determined is based on the data and how much information needs to be shared. Ideally the indexes will be aligned so that the data in a particular index interacts with data in other indexes as minimally as possible. At this point a sequence of operations is applied across these indexes. During occasions where data elements do need to be shared, performance can remain relatively intact based on shift operations and masking techniques[http://parlab.eecs.berkeley.edu/wiki/_media/patterns/data_parallel.pdf], as long as they are kept beneath a certain rate of occurrence. This data processing model lyes at the core of GPGPU and in conjunction with the SIMD execution model that contains its own specialized data structures and alignment operations combine to create a type of framework that APIs such as CUDA and OpenCL leverage to get peak performance out of the software applications that interface with them.		With the evolutions in GPU’s, especially in regards to their floating calculations, and also the software progressions made by Nvidia and Apple with their API’s to interface with this different type of hardware, made it very attractive to developers to try to take advantage. What all of these advances meant to the development community is that data parallelism had proven very powerful in the graphics rendering arena and could be leveraged for other types of application processing. From a high level, the algorithmic concept that these API’s take advantage of is data is arranged in data structures that can be executed in parallel. These data structures are aligned to an index space. How this index space is determined is based on the data and how much information needs to be shared. Ideally the indexes will be aligned so that the data in a particular index interacts with data in other indexes as minimally as possible. At this point a sequence of operations is applied across these indexes. During occasions where data elements do need to be shared, performance can remain relatively intact based on shift operations and masking techniques[http://parlab.eecs.berkeley.edu/wiki/_media/patterns/data_parallel.pdf], as long as they are kept beneath a certain rate of occurrence. This data processing model lyes at the core of GPGPU and in conjunction with the SIMD execution model that contains its own specialized data structures and alignment operations combine to create a type of framework that APIs such as CUDA and OpenCL leverage to get peak performance out of the software applications that interface with them.

	To give a bit more background on data parallelism we will discuss in a bit more detail how the process is achieved and how it has evolved. The first most basic scenario we will talk about is Oversubscription. If we think of each of our data structures that we have created along an index as a worker, and this collection of workers are all trying to complete a job, then In this type of parallelism, resources are allocated based on which worker has the most work to do. So all ~~off~~ the workers have the same amount of resources even though it is highly likely that very few of the workers actually need that amount of resources[https://wiki.aalto.fi/download/attachments/70779066/T-106.5840_2012_Halme.pdf?version=1&modificationDate=1357205607000]. It is a rather wasteful model as programmers will typically allocate many more sources than they will actually use but it helps illustrate the concept of how parallelism works. Moving from that example to Serialization helps a bit. In the model this workers run in parallel but individually execute sequentially. Now you are only allocated as many resources as each worker needs. We solved one challenge with Oversubscription but we still have another, and that is that each worker can have a very unbalanced workload compared to the other workers. We have no way of knowing if all of the workers are being utilized fully to get maximum efficiency. This is where the concept of flattening comes in. Here before the workload is distributed among the workers it is organized in evenly weighted vectors. This is why it is also referred to as vectorized parallelism[http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.118.9152&rep=rep1&type=pdf]. Here the workers do the same job as the previous models, but complication is introduced in accurately flattening the data and also extensive logging operations to keep track of how the work has been separated. Finally we have Dynamic Parallelism where we introduce a concept called work stealing. In this model, when a worker becomes overburdened they can divide out that work and spin up a new job. At that point another worker, perhaps one that is idle can take over that job thus relieving the initial worker from that burden. This dynamic model brings a lot of flexibility and elasticity to parallelism. The tradeoff to this is greater runtime analysis and logic supplied by the developer[http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.118.9152&rep=rep1&type=pdf].		To give a bit more background on data parallelism we will discuss in a bit more detail how the process is achieved and how it has evolved. The first most basic scenario we will talk about is Oversubscription. If we think of each of our data structures that we have created along an index as a worker, and this collection of workers are all trying to complete a job, then In this type of parallelism, resources are allocated based on which worker has the most work to do. So all of the workers have the same amount of resources even though it is highly likely that very few of the workers actually need that amount of resources[https://wiki.aalto.fi/download/attachments/70779066/T-106.5840_2012_Halme.pdf?version=1&modificationDate=1357205607000]. It is a rather wasteful model as programmers will typically allocate many more sources than they will actually use but it helps illustrate the concept of how parallelism works. Moving from that example to Serialization helps a bit. In the model this workers run in parallel but individually execute sequentially. Now you are only allocated as many resources as each worker needs. We solved one challenge with Oversubscription but we still have another, and that is that each worker can have a very unbalanced workload compared to the other workers. We have no way of knowing if all of the workers are being utilized fully to get maximum efficiency. This is where the concept of flattening comes in. Here before the workload is distributed among the workers it is organized in evenly weighted vectors. This is why it is also referred to as vectorized parallelism[http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.118.9152&rep=rep1&type=pdf]. Here the workers do the same job as the previous models, but complication is introduced in accurately flattening the data and also extensive logging operations to keep track of how the work has been separated. Finally we have Dynamic Parallelism where we introduce a concept called work stealing. In this model, when a worker becomes overburdened they can divide out that work and spin up a new job. At that point another worker, perhaps one that is idle can take over that job thus relieving the initial worker from that burden. This dynamic model brings a lot of flexibility and elasticity to parallelism. The tradeoff to this is greater runtime analysis and logic supplied by the developer[http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.118.9152&rep=rep1&type=pdf].

	[[File:DataParallelism_DataStructures.png\|center\|frame\|265x562px\|Data Parallelism Data Structures as shown in Functional Programming for Nested Data Parallelism on GPUs [https://wiki.aalto.fi/download/attachments/70779066/T-106.5840_2012_Halme.pdf?version=1&modificationDate=1357205607000]]]		[[File:DataParallelism_DataStructures.png\|center\|frame\|265x562px\|Data Parallelism Data Structures as shown in Functional Programming for Nested Data Parallelism on GPUs [https://wiki.aalto.fi/download/attachments/70779066/T-106.5840_2012_Halme.pdf?version=1&modificationDate=1357205607000]]]

Kcelrod2: /* Overview */

2013-02-10T23:56:55Z

Overview

← Older revision		Revision as of 23:56, 10 February 2013
Line 45:		Line 45:
	With the evolutions in GPU’s, especially in regards to their floating calculations, and also the software progressions made by Nvidia and Apple with their API’s to interface with this different type of hardware, made it very attractive to developers to try to take advantage. What all of these advances meant to the development community is that data parallelism had proven very powerful in the graphics rendering arena and could be leveraged for other types of application processing. From a high level, the algorithmic concept that these API’s take advantage of is data is arranged in data structures that can be executed in parallel. These data structures are aligned to an index space. How this index space is determined is based on the data and how much information needs to be shared. Ideally the indexes will be aligned so that the data in a particular index interacts with data in other indexes as minimally as possible. At this point a sequence of operations is applied across these indexes. During occasions where data elements do need to be shared, performance can remain relatively intact based on shift operations and masking techniques[http://parlab.eecs.berkeley.edu/wiki/_media/patterns/data_parallel.pdf], as long as they are kept beneath a certain rate of occurrence. This data processing model lyes at the core of GPGPU and in conjunction with the SIMD execution model that contains its own specialized data structures and alignment operations combine to create a type of framework that APIs such as CUDA and OpenCL leverage to get peak performance out of the software applications that interface with them.		With the evolutions in GPU’s, especially in regards to their floating calculations, and also the software progressions made by Nvidia and Apple with their API’s to interface with this different type of hardware, made it very attractive to developers to try to take advantage. What all of these advances meant to the development community is that data parallelism had proven very powerful in the graphics rendering arena and could be leveraged for other types of application processing. From a high level, the algorithmic concept that these API’s take advantage of is data is arranged in data structures that can be executed in parallel. These data structures are aligned to an index space. How this index space is determined is based on the data and how much information needs to be shared. Ideally the indexes will be aligned so that the data in a particular index interacts with data in other indexes as minimally as possible. At this point a sequence of operations is applied across these indexes. During occasions where data elements do need to be shared, performance can remain relatively intact based on shift operations and masking techniques[http://parlab.eecs.berkeley.edu/wiki/_media/patterns/data_parallel.pdf], as long as they are kept beneath a certain rate of occurrence. This data processing model lyes at the core of GPGPU and in conjunction with the SIMD execution model that contains its own specialized data structures and alignment operations combine to create a type of framework that APIs such as CUDA and OpenCL leverage to get peak performance out of the software applications that interface with them.

	To give a bit more background on data parallelism we will discuss in a bit more detail how the process is achieved and how it has evolved. The first, most basic scenario we will talk about is Oversubscription. If we think of each of our data structures that we have created along an index as a worker, and this collection of workers are all trying to complete a job, then In this type of parallelism, resources are allocated based on which worker has the most work to do. So all off the workers have the same amount of resources even though it is highly likely that very few of the workers actually need that amount of resources[https://wiki.aalto.fi/download/attachments/70779066/T-106.5840_2012_Halme.pdf?version=1&modificationDate=1357205607000]. It is a rather wasteful model as programmers will typically allocate many more sources than they will actually use but it helps illustrate the concept of how parallelism works. Moving from that example to Serialization helps a bit. In the model this workers run in parallel but individually execute sequentially. Now you are only allocated as many resources as each worker needs. We solved one challenge with Oversubscription but we still have another, and that is that each worker can have a very unbalanced workload compared to the other workers. We have no way of knowing if all of the workers are being utilized fully to get maximum efficiency. This is where the concept of flattening comes in. Here before the workload is distributed among the workers it is organized in evenly weighted vectors. This is why it is also referred to as vectorized parallelism[http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.118.9152&rep=rep1&type=pdf]. Here the workers do the same job as the previous models, but complication is introduced in accurately flattening the data and also extensive logging operations to keep track of how the work has been separated. Finally we have Dynamic Parallelism where we introduce a concept called work stealing. In this model, when a worker becomes overburdened they can divide out that work and spin up a new job. At that point another worker, perhaps one that is idle can take over that job thus relieving the initial worker from that burden. This dynamic model brings a lot of flexibility and elasticity to parallelism. The tradeoff to this is greater runtime analysis and logic supplied by the developer[http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.118.9152&rep=rep1&type=pdf].		To give a bit more background on data parallelism we will discuss in a bit more detail how the process is achieved and how it has evolved. The first most basic scenario we will talk about is Oversubscription. If we think of each of our data structures that we have created along an index as a worker, and this collection of workers are all trying to complete a job, then In this type of parallelism, resources are allocated based on which worker has the most work to do. So all off the workers have the same amount of resources even though it is highly likely that very few of the workers actually need that amount of resources[https://wiki.aalto.fi/download/attachments/70779066/T-106.5840_2012_Halme.pdf?version=1&modificationDate=1357205607000]. It is a rather wasteful model as programmers will typically allocate many more sources than they will actually use but it helps illustrate the concept of how parallelism works. Moving from that example to Serialization helps a bit. In the model this workers run in parallel but individually execute sequentially. Now you are only allocated as many resources as each worker needs. We solved one challenge with Oversubscription but we still have another, and that is that each worker can have a very unbalanced workload compared to the other workers. We have no way of knowing if all of the workers are being utilized fully to get maximum efficiency. This is where the concept of flattening comes in. Here before the workload is distributed among the workers it is organized in evenly weighted vectors. This is why it is also referred to as vectorized parallelism[http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.118.9152&rep=rep1&type=pdf]. Here the workers do the same job as the previous models, but complication is introduced in accurately flattening the data and also extensive logging operations to keep track of how the work has been separated. Finally we have Dynamic Parallelism where we introduce a concept called work stealing. In this model, when a worker becomes overburdened they can divide out that work and spin up a new job. At that point another worker, perhaps one that is idle can take over that job thus relieving the initial worker from that burden. This dynamic model brings a lot of flexibility and elasticity to parallelism. The tradeoff to this is greater runtime analysis and logic supplied by the developer[http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.118.9152&rep=rep1&type=pdf].

	[[File:DataParallelism_DataStructures.png\|center\|frame\|265x562px\|Data Parallelism Data Structures as shown in Functional Programming for Nested Data Parallelism on GPUs [https://wiki.aalto.fi/download/attachments/70779066/T-106.5840_2012_Halme.pdf?version=1&modificationDate=1357205607000]]]		[[File:DataParallelism_DataStructures.png\|center\|frame\|265x562px\|Data Parallelism Data Structures as shown in Functional Programming for Nested Data Parallelism on GPUs [https://wiki.aalto.fi/download/attachments/70779066/T-106.5840_2012_Halme.pdf?version=1&modificationDate=1357205607000]]]

Kcelrod2: /* History */

2013-02-10T23:54:56Z

History

← Older revision		Revision as of 23:54, 10 February 2013
Line 12:		Line 12:

	=History=		=History=
	In the the nineties 3 dimensional rendering was in high demand as the next step in graphical performance. Based on this demand, programming interfaces emerged called OpenGL and DirectX. OpenGL is a language independent, platform independent collections of functions which can be called by a client application to render 2D and 3D graphics. Because OpenGL[http://en.wikipedia.org/wiki/OpenGL] is language independent many 3rd parties right extensions to the language or interface with it using their own API’s (javascript would be an example of this). DirectX[http://en.wikipedia.org/wiki/DirectX] is Microsofts platform specific version of this same concept which made it’s debut as part of Window 95 to help incentivize the Windows platform for game developers who were more likely to write games for DOS due to its allowance of direct access to the graphics hardware. Both technologies are built with rendering power and efficiency as their central focus.		In the the nineties three-dimensional rendering was in high demand as the next step in graphical performance. Based on this demand, programming interfaces emerged called OpenGL and DirectX. OpenGL is a language independent, platform independent collections of functions which can be called by a client application to render 2D and 3D graphics. Because OpenGL[http://en.wikipedia.org/wiki/OpenGL] is language independent many 3rd parties right extensions to the language or interface with it using their own API’s (javascript would be an example of this). DirectX[http://en.wikipedia.org/wiki/DirectX] is Microsofts platform specific version of this same concept which made it’s debut as part of Window 95 to help incentivize the Windows platform for game developers who were more likely to write games for DOS due to its allowance of direct access to the graphics hardware. Both technologies are built with rendering power and efficiency as their central focus.

	At the turn of the 21st century the two major companies in the GPU industry emerged as Nvidia and ATI both made great strides in allowing developers access to the graphics rendering hardware. Nvidia began allowing developers to insert small chunks of code into the graphics pipeline giving them programmable control over shaders. ATI were next contribute this evolution when they were the first to support floating point calculations in the hardware. This opened the door for more realistic graphics rendering and modeling. Even with these notable steps, developers were still very restricted about how many instructions they could write and what functions were supported. It was enough to entice developers but they were still quite limited.		At the turn of the 21st century the two major companies in the GPU industry emerged as Nvidia and ATI both made great strides in allowing developers access to the graphics rendering hardware. Nvidia began allowing developers to insert small chunks of code into the graphics pipeline giving them programmable control over shaders. ATI were next contribute this evolution when they were the first to support floating point calculations in the hardware. This opened the door for more realistic graphics rendering and modeling. Even with these notable steps, developers were still very restricted about how many instructions they could write and what functions were supported. It was enough to entice developers but they were still quite limited.

Skey: /* Examples: */

2013-02-10T23:51:30Z

Examples:

← Older revision		Revision as of 23:51, 10 February 2013
Line 90:		Line 90:
	[[File:PortableLDPCDecodingOnMulticoresUsingOpenCL.png\|center\|frame\|959x630px\|OpenCL runtime as seen in Portable LDPC Decoding on Multicores Using OpenCL[http://en.wikipedia.org/wiki/OpenCL]]]		[[File:PortableLDPCDecodingOnMulticoresUsingOpenCL.png\|center\|frame\|959x630px\|OpenCL runtime as seen in Portable LDPC Decoding on Multicores Using OpenCL[http://en.wikipedia.org/wiki/OpenCL]]]

	An OpenCL program is similar to some other low level languages. It has a main routine that is executed on a host. When this main routine reaches a section of the code written for parallel execution the parallel kernel is launches on the GPU where it is executed using a multithreaded execution model. Typically a programmer will define sections of the code that are meant for parallel processing. These definitions are picked up by the compiler which loads these as kernels to be executed on several threads. Once the kernel is executing it will adapt dynamically to evenly distribute the work. This requires the programs to be able to identify how many cores are on the system and how the algorithm should be partitioned. It should also be able to query the environment or context of the multicore system. Since OpenCL has all of these functions available to it through its APIs the OpenCL task scheduler splits the workload to do balanced computation. This functionality is also open to the developer if they would like to decide this logic themselves. Data to be executed in parallel is passed into memory using OpenCL functions such as clEnqueueWriteBuffer and then passed back to the main routine with a similar function clEnqueueReadBuffer. An example routine that illustrates data parallelism is below[http://en.wikipedia.org/wiki/OpenCL]:		An OpenCL program is similar to some other low level languages. It has a main routine that is executed on a host. When this main routine reaches a section of the code written for parallel execution the parallel kernel launches on the GPU where it is executed using a multithreaded execution model. Typically a programmer will define sections of the code that are meant for parallel processing. These definitions are picked up by the compiler which loads these as kernels to be executed on several threads. Once the kernel is executing it will adapt dynamically to evenly distribute the work. This requires the programs to be able to identify how many cores are on the system and how the algorithm should be partitioned. It should also be able to query the environment or context of the multicore system. Since OpenCL has all of these functions available to it through its APIs the OpenCL task scheduler splits the workload to do balanced computation. This functionality is also open to the developer if they would like to decide this logic themselves. Data to be executed in parallel is passed into memory using OpenCL functions such as clEnqueueWriteBuffer and then passed back to the main routine with a similar function clEnqueueReadBuffer. An example routine that illustrates data parallelism is below[http://en.wikipedia.org/wiki/OpenCL]:

	<pre>		<pre>

Skey: /* OpenCL */

2013-02-10T23:48:54Z

OpenCL

← Older revision		Revision as of 23:48, 10 February 2013
Line 52:		Line 52:

	==OpenCL==		==OpenCL==
	OpenCL[http://en.wikipedia.org/wiki/OpenCL] is an open standard collection of API’s that is supported by several graphics hardware vendors and more recently large technology companies who are interested in GPGPU to improve efficiency and gain an edge in the high performance market. It is maintained by the Khronos group and has become an industry standard. OpenCL provides programming API’s so that C and C++ developers can write logic that is executed on a variety of microprocessor designs including GPUs. It provides a core functionality that is supported across hardware vendors and also includes specialized functions for specific hardware environments to allow the developer the opportunity to tune performance. The hardware and especially the GPU market is rapidly evolving and makes the challenge of supporting all different hardware configurations nearly impossible. The biggest strength of OpenCL is that provides a standard interface where a developer can create efficient instructions that are correct and portable across vary hardware specifications. This industry standard makes it ideal for us to look at in our discussion of data parallelism.		OpenCL[http://en.wikipedia.org/wiki/OpenCL] is an open standard collection of API’s that is supported by several graphics hardware vendors and more recently large technology companies who are interested in GPGPU to improve efficiency and gain an edge in the high performance market. It is maintained by the Khronos group and has become an industry standard. OpenCL provides programming API’s so that C and C++ developers can write logic that is executed on a variety of microprocessor designs including GPUs. It provides a core functionality that is supported across hardware vendors and also includes specialized functions for specific hardware environments to allow the developer the opportunity to tune performance. The hardware and especially the GPU market is rapidly evolving and makes the challenge of supporting all different hardware configurations nearly impossible. The biggest strength of OpenCL is that it provides a standard interface where a developer can create efficient instructions that are correct and portable across vary hardware specifications. This industry standard makes it ideal for us to look at in our discussion of data parallelism.

	Because OpenCL strives to be hardware agnostic it encourages run-time compilation and at that moment the runtime will take advantage of that particular device’s hardware and software features. Although correctness and portability are supported, peak performance is not guaranteed. While OpenCL will attempt to take advantage of all the device hardware configuration has to offer at runtime, intervention by the developer to write specific functions that work most efficiently on that hardware may still be necessary for optimal performance.		Because OpenCL strives to be hardware agnostic it encourages run-time compilation and at that moment the runtime will take advantage of that particular device’s hardware and software features. Although correctness and portability are supported, peak performance is not guaranteed. While OpenCL will attempt to take advantage of all the device hardware configuration has to offer at runtime, intervention by the developer to write specific functions that work most efficiently on that hardware may still be necessary for optimal performance.

Skey: /* Overview */

2013-02-10T23:46:43Z

Overview

← Older revision		Revision as of 23:46, 10 February 2013
Line 45:		Line 45:
	With the evolutions in GPU’s, especially in regards to their floating calculations, and also the software progressions made by Nvidia and Apple with their API’s to interface with this different type of hardware, made it very attractive to developers to try to take advantage. What all of these advances meant to the development community is that data parallelism had proven very powerful in the graphics rendering arena and could be leveraged for other types of application processing. From a high level, the algorithmic concept that these API’s take advantage of is data is arranged in data structures that can be executed in parallel. These data structures are aligned to an index space. How this index space is determined is based on the data and how much information needs to be shared. Ideally the indexes will be aligned so that the data in a particular index interacts with data in other indexes as minimally as possible. At this point a sequence of operations is applied across these indexes. During occasions where data elements do need to be shared, performance can remain relatively intact based on shift operations and masking techniques[http://parlab.eecs.berkeley.edu/wiki/_media/patterns/data_parallel.pdf], as long as they are kept beneath a certain rate of occurrence. This data processing model lyes at the core of GPGPU and in conjunction with the SIMD execution model that contains its own specialized data structures and alignment operations combine to create a type of framework that APIs such as CUDA and OpenCL leverage to get peak performance out of the software applications that interface with them.		With the evolutions in GPU’s, especially in regards to their floating calculations, and also the software progressions made by Nvidia and Apple with their API’s to interface with this different type of hardware, made it very attractive to developers to try to take advantage. What all of these advances meant to the development community is that data parallelism had proven very powerful in the graphics rendering arena and could be leveraged for other types of application processing. From a high level, the algorithmic concept that these API’s take advantage of is data is arranged in data structures that can be executed in parallel. These data structures are aligned to an index space. How this index space is determined is based on the data and how much information needs to be shared. Ideally the indexes will be aligned so that the data in a particular index interacts with data in other indexes as minimally as possible. At this point a sequence of operations is applied across these indexes. During occasions where data elements do need to be shared, performance can remain relatively intact based on shift operations and masking techniques[http://parlab.eecs.berkeley.edu/wiki/_media/patterns/data_parallel.pdf], as long as they are kept beneath a certain rate of occurrence. This data processing model lyes at the core of GPGPU and in conjunction with the SIMD execution model that contains its own specialized data structures and alignment operations combine to create a type of framework that APIs such as CUDA and OpenCL leverage to get peak performance out of the software applications that interface with them.

	To give a bit more background on data parallelism we will discuss in a bit more detail how the process is achieved and how it has evolved. The first, most basic scenario we will talk about is Oversubscription. If we think of each of our data structures that we have created along an index as a worker, and this collection of workers are all trying to complete a job, then In this type of parallelism, resources are allocated based on which worker has the most work to do. So all off the workers have the same amount of resources even though it is highly likely that very few of the workers actually need that amount of resources[https://wiki.aalto.fi/download/attachments/70779066/T-106.5840_2012_Halme.pdf?version=1&modificationDate=1357205607000]. It is a rather wasteful model as programmers will typically allocate many more sources than they will actually use but it helps illustrate the concept of how parallelism works. Moving from that example to Serialization helps a bit. In the model ~~the~~ workers run in parallel but individually execute sequentially. Now you are only allocated as many resources as each worker needs. We solved one challenge with Oversubscription but we still have another, and that is that each worker can have a very unbalanced workload compared to the other workers. We have no way of knowing if all of the workers are being utilized fully to get maximum efficiency. This is where the concept of flattening comes in. Here before the workload is distributed among the workers it is organized in evenly weighted vectors. This is why it is also referred to as vectorized parallelism[http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.118.9152&rep=rep1&type=pdf]. Here the workers do the same job as the previous models, but complication is introduced in accurately flattening the data and also extensive logging operations to keep track of how the work has been separated. Finally we have Dynamic Parallelism where we introduce a concept called work stealing. In this model, when a worker becomes overburdened they can divide out that work and spin up a new job. At that point another worker, perhaps one that is idle can take over that job thus relieving the initial worker from that burden. This dynamic model brings a lot of flexibility and elasticity to parallelism. The tradeoff to this greater runtime analysis and logic supplied by the developer[http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.118.9152&rep=rep1&type=pdf].		To give a bit more background on data parallelism we will discuss in a bit more detail how the process is achieved and how it has evolved. The first, most basic scenario we will talk about is Oversubscription. If we think of each of our data structures that we have created along an index as a worker, and this collection of workers are all trying to complete a job, then In this type of parallelism, resources are allocated based on which worker has the most work to do. So all off the workers have the same amount of resources even though it is highly likely that very few of the workers actually need that amount of resources[https://wiki.aalto.fi/download/attachments/70779066/T-106.5840_2012_Halme.pdf?version=1&modificationDate=1357205607000]. It is a rather wasteful model as programmers will typically allocate many more sources than they will actually use but it helps illustrate the concept of how parallelism works. Moving from that example to Serialization helps a bit. In the model this workers run in parallel but individually execute sequentially. Now you are only allocated as many resources as each worker needs. We solved one challenge with Oversubscription but we still have another, and that is that each worker can have a very unbalanced workload compared to the other workers. We have no way of knowing if all of the workers are being utilized fully to get maximum efficiency. This is where the concept of flattening comes in. Here before the workload is distributed among the workers it is organized in evenly weighted vectors. This is why it is also referred to as vectorized parallelism[http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.118.9152&rep=rep1&type=pdf]. Here the workers do the same job as the previous models, but complication is introduced in accurately flattening the data and also extensive logging operations to keep track of how the work has been separated. Finally we have Dynamic Parallelism where we introduce a concept called work stealing. In this model, when a worker becomes overburdened they can divide out that work and spin up a new job. At that point another worker, perhaps one that is idle can take over that job thus relieving the initial worker from that burden. This dynamic model brings a lot of flexibility and elasticity to parallelism. The tradeoff to this is greater runtime analysis and logic supplied by the developer[http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.118.9152&rep=rep1&type=pdf].

	[[File:DataParallelism_DataStructures.png\|center\|frame\|265x562px\|Data Parallelism Data Structures as shown in Functional Programming for Nested Data Parallelism on GPUs [https://wiki.aalto.fi/download/attachments/70779066/T-106.5840_2012_Halme.pdf?version=1&modificationDate=1357205607000]]]		[[File:DataParallelism_DataStructures.png\|center\|frame\|265x562px\|Data Parallelism Data Structures as shown in Functional Programming for Nested Data Parallelism on GPUs [https://wiki.aalto.fi/download/attachments/70779066/T-106.5840_2012_Halme.pdf?version=1&modificationDate=1357205607000]]]

Skey: /* Overview */

2013-02-10T23:43:36Z

Overview

← Older revision		Revision as of 23:43, 10 February 2013
Line 43:		Line 43:
	=GPGPU Data Parallelism=		=GPGPU Data Parallelism=
	==Overview==		==Overview==
	With the evolutions in GPU’s, especially in regards to their floating calculations, and also the software progressions made by Nvidia and Apple with their API’s to interface with this different type of hardware, made it very attractive to developers to try to take advantage. What all of these advances meant to the development community is that data parallelism had proven very powerful in the graphics rendering arena and could be leveraged for other types of application processing. From a high level, the algorithmic concept that these API’s take advantage of is data is arranged in data structures that can be executed in parallel. These data structures are aligned to an index space. How this index space is determined is based on the data and how much information needs to be shared. Ideally the indexes will be aligned so that the data in a particular index interacts with data in other indexes as minimally as possible. At this point a sequence of operations is applied across these indexes. During occasions where data elements do need to be shared, performance can remain relatively intact based on shift operations and masking techniques[http://parlab.eecs.berkeley.edu/wiki/_media/patterns/data_parallel.pdf], as long as they are kept beneath certain rate of occurrence. This data processing model lyes at the core of GPGPU and in conjunction with the SIMD execution model that contains its own specialized data structures and alignment operations combine to create a type of framework that APIs such as CUDA and OpenCL leverage to get peak performance out of the software applications that interface with them.		With the evolutions in GPU’s, especially in regards to their floating calculations, and also the software progressions made by Nvidia and Apple with their API’s to interface with this different type of hardware, made it very attractive to developers to try to take advantage. What all of these advances meant to the development community is that data parallelism had proven very powerful in the graphics rendering arena and could be leveraged for other types of application processing. From a high level, the algorithmic concept that these API’s take advantage of is data is arranged in data structures that can be executed in parallel. These data structures are aligned to an index space. How this index space is determined is based on the data and how much information needs to be shared. Ideally the indexes will be aligned so that the data in a particular index interacts with data in other indexes as minimally as possible. At this point a sequence of operations is applied across these indexes. During occasions where data elements do need to be shared, performance can remain relatively intact based on shift operations and masking techniques[http://parlab.eecs.berkeley.edu/wiki/_media/patterns/data_parallel.pdf], as long as they are kept beneath a certain rate of occurrence. This data processing model lyes at the core of GPGPU and in conjunction with the SIMD execution model that contains its own specialized data structures and alignment operations combine to create a type of framework that APIs such as CUDA and OpenCL leverage to get peak performance out of the software applications that interface with them.

	To give a bit more background on data parallelism we will discuss in a bit more detail how the process is achieved and how it has evolved. The first, most basic scenario we will talk about is Oversubscription. If we think of each of our data structures that we have created along an index as a worker, and this collection of workers are all trying to complete a job, then In this type of parallelism, resources are allocated based on which worker has the most work to do. So all off the workers have the same amount of resources even though it is highly likely that very few of the workers actually need that amount of resources[https://wiki.aalto.fi/download/attachments/70779066/T-106.5840_2012_Halme.pdf?version=1&modificationDate=1357205607000]. It is a rather wasteful model as programmers will typically allocate many more sources than they will actually use but it helps illustrate the concept of how parallelism works. Moving from that example to Serialization helps a bit. In the model the workers run in parallel but individually execute sequentially. Now you are only allocated as many resources as each worker needs. We solved one challenge with Oversubscription but we still have another, and that is that each worker can have a very unbalanced workload compared to the other workers. We have no way of knowing if all of the workers are being utilized fully to get maximum efficiency. This is where the concept of flattening comes in. Here before the workload is distributed among the workers it is organized in evenly weighted vectors. This is why it is also referred to as vectorized parallelism[http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.118.9152&rep=rep1&type=pdf]. Here the workers do the same job as the previous models, but complication is introduced in accurately flattening the data and also extensive logging operations to keep track of how the work has been separated. Finally we have Dynamic Parallelism where we introduce a concept called work stealing. In this model, when a worker becomes overburdened they can divide out that work and spin up a new job. At that point another worker, perhaps one that is idle can take over that job thus relieving the initial worker from that burden. This dynamic model brings a lot of flexibility and elasticity to parallelism. The tradeoff to this greater runtime analysis and logic supplied by the developer[http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.118.9152&rep=rep1&type=pdf].		To give a bit more background on data parallelism we will discuss in a bit more detail how the process is achieved and how it has evolved. The first, most basic scenario we will talk about is Oversubscription. If we think of each of our data structures that we have created along an index as a worker, and this collection of workers are all trying to complete a job, then In this type of parallelism, resources are allocated based on which worker has the most work to do. So all off the workers have the same amount of resources even though it is highly likely that very few of the workers actually need that amount of resources[https://wiki.aalto.fi/download/attachments/70779066/T-106.5840_2012_Halme.pdf?version=1&modificationDate=1357205607000]. It is a rather wasteful model as programmers will typically allocate many more sources than they will actually use but it helps illustrate the concept of how parallelism works. Moving from that example to Serialization helps a bit. In the model the workers run in parallel but individually execute sequentially. Now you are only allocated as many resources as each worker needs. We solved one challenge with Oversubscription but we still have another, and that is that each worker can have a very unbalanced workload compared to the other workers. We have no way of knowing if all of the workers are being utilized fully to get maximum efficiency. This is where the concept of flattening comes in. Here before the workload is distributed among the workers it is organized in evenly weighted vectors. This is why it is also referred to as vectorized parallelism[http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.118.9152&rep=rep1&type=pdf]. Here the workers do the same job as the previous models, but complication is introduced in accurately flattening the data and also extensive logging operations to keep track of how the work has been separated. Finally we have Dynamic Parallelism where we introduce a concept called work stealing. In this model, when a worker becomes overburdened they can divide out that work and spin up a new job. At that point another worker, perhaps one that is idle can take over that job thus relieving the initial worker from that burden. This dynamic model brings a lot of flexibility and elasticity to parallelism. The tradeoff to this greater runtime analysis and logic supplied by the developer[http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.118.9152&rep=rep1&type=pdf].