Expertiza_Wiki - User contributions [en]

CSC/ECE 506 Fall 2007/wiki2 aY3w

2007-10-19T01:15:11Z

Jfswaffo: CSC/ECE 506 Fall 2007/wiki2 aY3w moved to CSC/ECE 506 Fall 2007/wiki3 2 aY3w: professor's instructions

#REDIRECT [[CSC/ECE 506 Fall 2007/wiki3 2 aY3w]]

CSC/ECE 506 Fall 2007/wiki3 2 aY3w

2007-10-19T01:15:11Z

Jfswaffo: CSC/ECE 506 Fall 2007/wiki2 aY3w moved to CSC/ECE 506 Fall 2007/wiki3 2 aY3w: professor's instructions

SCI. The IEEE Scalable Coherent Interface is a superset of the SSCI protocol we have been considering in class. A lot has been written about it, but it is still difficult to comprehend. Using SSCI as a starting point, explain why additional states are necessary, and give (or cite) examples that demonstrate how they work. Ideally, this would still be an overview of the working of the protocol, referencing more detailed documentation on the Web.

=== A Brief Overview of the SSCI Protocol ===

The Simple Scalable Coherence Interface (SSCI) protocol is a simplified version of the SCI protocol. While the SCI protocol has 29 stable states and many pending states, the SSCI protocol has only 3 states. Consequently, many race conditions are possible. Here we give a brief overview of the SSCI protocol, and elaborate on some possible race conditions in the final section. 
 
The caches themselves follow the MESI protocol, and thus are in one of those four states. Each block of cached data has a list of sharers, or processors that have that block cached. This list is represented as a doubly linked list that is distributed among the sharers themselves. 

In addition to the MESI state, each cache maintains a "next" pointer and a "previous" pointer. Each pointer points to another node in the list of sharers of the cached block of data. The head of the list will have a previous pointer value of 0, and the tail of the list will have a next pointer value of 0. 

Each block of data has a "home directory," located in some (possibly remote) memory location. The home directory is normally computable by the memory address of the block of data. If the block is cached, the home directory will contain the head pointer of the list of sharers. Additionally, the home directory will contain state information for the block.
As previously stated, in the SSCI protocol the memory directory is in one of three states. They are: 

<ul>
<li>UNOWNED - the block is unowned by any cache.</li>
<li>SHARED - the block is owned by multiple caches. Main memory is up to date.</li>
<li>EXCLUSIVE/MODIFIED - the (possibly dirty) block is owned by a single cache. Main memory is possibly out of date.</li>
</ul>

<hr>
=== A Brief Overview of the SCI Protocol ===

In this section we give a very brief overview of the SCI protocol. This is not meant to be a complete description, but to give enough information to illustrate some key differences in the SSCI and SCI protocols. 

==== Memory Directory States ====
Similar to the SSCI protocol, in SCI the memory directory is one of three states:
 
<ul>
<li>HOME - no remote cache contains a copy of the block.</li>
<li>FRESH - one of more remote caches may have a read-only copy of the block. Main memory is up to date.</li>
<li>GONE - the cache at the head of the sharing list contains an exclusive (possibly dirty) copy of the block.</li>
</ul>

==== Cache States ====
Additionally, each cache has a state, either stable or pending. Stable states have two parts: 
<ol>
<li>Where the cache entry is located in the sharing list for that block</li>
<ul>
<li>ONLY - singleton list</li>
<li>HEAD - head of sharing list of more than one node</li>
<li>MID - not head or tail of sharing list of more than one node</li>
<li>TAIL - tail of sharing list of more than one node</li>
</ul>
<li>State of the cached block</li>
<ul>
<li>DIRTY - modified and writable</li>
<li>CLEAN - unmodified and writable, same contents as memory</li>
<li>FRESH - data is readable and writable, but memory must be informed before memory is written</li>
<li>COPY - unmodified and readable</li>
<li>many others</li>
</ul>
</ol>

These two parts together describe the cache state, e.g. FRESH-ONLY or MID-VALID.

==== List Operations ====
SCI defines three primitive list operations for shared lists:
<ol>
<li>List construction - adding a new node to the head of the sharing list</li>
<li>Rollout - removing a node from the sharing list</li>
<li>Invalidation - invalidate all other sharers. Can only be performed by the head node.</li>
</ol>

The head of the list of sharers can be thought of as the owner. Only the head can modify the cached data. If some other sharer wants to modify the data, it must first rollout of the list and reattach as the head. 

<hr>
=== Why Additional States are Needed ===

The principle difference between SCI and SSCI is that SCI provides mechanisms for '''resolving race conditions''' and '''preserving serialization'''.

==== Example 1 ====
Suppose some processor, say P1, issues a read request and misses on some block that is not cached by any processor. So, the block will have to be fetched from main memory and the line will be put into P1's local cache. Space will have to be allocated in P1's cache, usually by evicting some other line. 

In the SSCI protocol, P1 will send a READ message to the home directory. The home directory will reply with the data and set its state to EM, and its head pointer to 1. Upon receipt, P1 will put the block in the allocated line, set its state to E (from the MESI protocol), and its next/previous pointers to 0. 

Consider what might happen if two processors both read miss concurrently. 
<ul>
<li>P1 sends a READ request to the home node.</li>
<li>Concurrently, P2 sends a READ request to the home node.</li>
<li>The home node receives the request from P1.</li>
<li>The home node sets its state to EM, its head pointer to 1 (P1), and sends the data to P1.</li>
<li>The home node receives the request from P2.</li>
<li>The home node sends a ReplyID to P2, informing it that P1 "owns" the data.</li>
<li>P2 receives the ReplyID and sends WB+Int+UpdPtr to P1.</li>
<li>P1 receives the message from P2</li>
<li>ERROR! P1 hasn't yet received the ReplyD from the home directory!</li>
</ul>

Due to network latency, it's possible that network messages are received "out of order," causing race conditions such as the one above. 

Now let's consider the same scenario in SCI. 

<ul>
<li>P1 and P2 both read miss.</li>
<li>P1 and P2 set aside space for the line to be read in (possibly by evicting another line).</li>
<li>P1 and P2 concurrently set the state of that line to a "pending" state, and issue a read request to the home node.</li>
<li>The home node receives the request from P1. Since the block is not cached anywhere, the memory directory will be in state HOME.</li>
<li>The home node sets its state to FRESH, its head pointer to 1, and replies to P1 with the data.</li>
<li>The home node receives P2's READ. Since the home node is in state FRESH, its data is up to date.</li>
<li>The home node sets its head pointer to 2 and replies to P2 with the data, and the "old" head pointer (P1).</li>
<li>P2 receives the data, but the action is not complete until it receives "permission" from P1 to become the new head of the list.</li>
<li>P2 remains in a pending state and sends a request to P1 to become the new head of the list.</li>
<li>P1 receives the request from P2, but is since it hasn't yet received the reply from the home directory it is still in a pending state.</li>
<li>P1 "extends" the pending list backwards. That is, P2 will be put at the head of the list, but in a "pending" state.</li>
<li>P1 receives the reply from the home directory and becomes the "true" head of the list. Even though P2 is ahead of P1 in the list, it's not the "true head," but a part of the "pending list."</li>
<li>P1 passes the "true head" status on to P2.</li>
</ul>

By maintaining a "pending list" and a "true head", read requests are atomic and we avoid the race condition sufferred under the SSCI protocol (albeit by adding more complexity). 

==== Example 2 ====

Suppose some block of data is being shared among several caches. Our linked list of sharers is P1-P2-P3-P4-P5. P3 needs to purge the line containing that block of data. 

Under the SSCI protocol, P3 will send an UpdPtr message to the processors represented by the previous and next pointers (P2 and P4 respectively). P2 will set its next pointer to P4, and P4 will set its previous pointer to P2. 

Consider what might happen if P3 and P4 concurrently purge their lines of shared data.
<ul>
<li>P3 sends UpdPtr(P3->P2) and UpdPtr(P3->P4) and purges its data</li>
<li>Concurrently, P4 sends UpdPtr(P4->P3) and UpdPtr(P4->P5) and purges its data</li>
<li>P2 received the UpdPtr from P3 and sets its "next" pointer to P4</li>
<li>ERROR! P4 does not have the line cached!</li>
</ul>
Since P4 has already purged and is no longer in the list of sharers, we have a race condition. 
Now let's examine the same scenario under the SCI protocol. In the SCI protocol, a node that wants to "roll out" is put in a pending state until it receives acknowledgment from both the next and previous nodes. 
<ul>
<li>P3 and P4 both put themselves in a pending state.</li>
<li>P3 sends UpdPtr(P3->P2) and UpdPtr(P3->P4)</li>
<li>Concurrently, P4 sends UpdPtr(P4->P3) and UpdPtr(P4->P5)</li>
<li>Deadlock! Neither P3 nor P4 will respond to the other while in a pending state.</li>
<li>Resolution: the node nearer to the tail of the list (P4) is given priority.</li>
<li>P3 must wait until P4 completes its rollout, giving a shared list of P1-P2-P3-P5.</li>
<li>P3 rolls out.</li>
</ul>

So, pending states are necessary to preserve a correct representation of the shared list, but even then we must deal with deadlock resolution. 

=== Links ===

http://www.scizzl.com/WhatIsSCI.html 
http://www.lrr.in.tum.de/~gerndt/home/Teaching/scalable_shared_memory_systems/Kapitel8.pdf 
http://csdl2.computer.org/persagen/DLAbsToc.jsp?resourcePath=/dl/mags/mi/&toc=comp/mags/mi/1992/01/m1toc.xml&DOI=10.1109/40.124376 
http://www.hcs.ufl.edu/SCI_Internal/

CSC/ECE 506 Fall 2007/wiki3 2 aY3w

2007-10-17T21:22:23Z

Jfswaffo:

CSC/ECE 506 Fall 2007/wiki3 2 aY3w

2007-10-17T21:20:29Z

Jfswaffo:

SCI. The IEEE Scalable Coherent Interface is a superset of the SSCI protocol we have been considering in class. A lot has been written about it, but it is still difficult to comprehend. Using SSCI as a starting point, explain why additional states are necessary, and give (or cite) examples that demonstrate how they work. Ideally, this would still be an overview of the working of the protocol, referencing more detailed documentation on the Web.

=== A Brief Overview of the SSCI Protocol ===

The Simple Scalable Coherence Interface (SSCI) protocol is a simplified version of the SCI protocol. While the SCI protocol has 29 stable states and many pending states, the SSCI protocol has only 3 states. Consequently, many race conditions are possible. Here we give a brief overview of the SSCI protocol, and elaborate on some possible race conditions in the final section. 
 
The caches themselves follow the MESI protocol, and thus are in one of those four states. Each block of cached data has a list of sharers, or processors that have that block cached. This list is represented as a doubly linked list that is distributed among the sharers themselves. 

In addition to the MESI state, each cache maintains a "next" pointer and a "previous" pointer. Each pointer points to another node in the list of sharers of the cached block of data. The head of the list will have a previous pointer value of 0, and the tail of the list will have a next pointer value of 0. 

Each block of data has a "home directory," located in some (possibly remote) memory location. The home directory is normally computable by the memory address of the block of data. If the block is cached, the home directory will contain the head pointer of the list of sharers. Additionally, the home directory will contain state information for the block.
As previously stated, in the SSCI protocol the memory directory is in one of three states. They are: 

<ul>
<li>UNOWNED - the block is unowned by any cache.</li>
<li>SHARED - the block is owned by multiple caches. Main memory is up to date.</li>
<li>EXCLUSIVE/MODIFIED - the (possibly dirty) block is owned by a single cache. Main memory is possibly out of date.</li>
</ul>

<hr>
=== A Brief Overview of the SCI Protocol ===

In this section we give a very brief overview of the SCI protocol. This is not meant to be a complete description, but to give enough information to illustrate some key differences in the SSCI and SCI protocols. 

==== Memory Directory States ====
Similar to the SSCI protocol, in SCI the memory directory is one of three states:
 
<ul>
<li>HOME - no remote cache contains a copy of the block.</li>
<li>FRESH - one of more remote caches may have a read-only copy of the block. Main memory is up to date.</li>
<li>GONE - the cache at the head of the sharing list contains an exclusive (possibly dirty) copy of the block.</li>
</ul>

==== Cache States ====
Additionally, each cache has a state, either stable or pending. Stable states have two parts: 
<ol>
<li>Where the cache entry is located in the sharing list for that block</li>
<ul>
<li>ONLY - singleton list</li>
<li>HEAD - head of sharing list of more than one node</li>
<li>MID - not head or tail of sharing list of more than one node</li>
<li>TAIL - tail of sharing list of more than one node</li>
</ul>
<li>State of the cached block</li>
<ul>
<li>DIRTY - modified and writable</li>
<li>CLEAN - unmodified and writable, same contents as memory</li>
<li>FRESH - data is readable and writable, but memory must be informed before memory is written</li>
<li>COPY - unmodified and readable</li>
<li>many others</li>
</ul>
</ol>

These two parts together describe the cache state, e.g. FRESH-ONLY or MID-VALID.

==== List Operations ====
SCI defines three primitive list operations for shared lists:
<ol>
<li>List construction - adding a new node to the head of the sharing list</li>
<li>Rollout - removing a node from the sharing list</li>
<li>Invalidation - invalidate all other sharers. Can only be performed by the head node.</li>
</ol>

The head of the list of sharers can be thought of as the owner. Only the head can modify the cached data. If some other sharer wants to modify the data, it must first rollout of the list and reattach as the head. 

<hr>
=== Why Additional States are Needed ===

The principle difference between SCI and SSCI is that SCI provides mechanisms for '''resolving race conditions''' and '''preserving serialization'''.

==== Example 1 ====
Suppose some processor, say P1, issues a read request and misses on some block that is not cached by any processor. So, the block will have to be fetched from main memory and the line will be put into P1's local cache. Space will have to be allocated in P1's cache, usually by evicting some other line. 

In the SSCI protocol, P1 will send a READ message to the home directory. The home directory will reply with the data and set its state to EM, and its head pointer to 1. Upon receipt, P1 will put the block in the allocated line, set its state to E (from the MESI protocol), and its next/previous pointers to 0. 

Consider what might happen if two processors both read miss concurrently. 
<ul>
<li>P1 sends a READ request to the home node.</li>
<li>Concurrently, P2 sends a READ request to the home node.</li>
<li>The home node receives the request from P1.</li>
<li>The home node sets its state to EM, its head pointer to 1 (P1), and sends the data to P1.</li>
<li>The home node receives the request from P2.</li>
<li>The home node sends a ReplyID to P2, informing it that P1 "owns" the data.</li>
<li>P2 receives the ReplyID and sends WB+Int+UpdPtr to P1.</li>
<li>P1 receives the message from P2</li>
<li>ERROR! P1 hasn't yet received the ReplyD from the home directory!</li>
</ul>

Due to network latency, it's possible that network messages are received "out of order," causing race conditions such as the one above. 

Now let's consider the same scenario in SCI. 

<ul>
<li>P1 and P2 both read miss.</li>
<li>P1 and P2 set aside space for the line to be read in (possibly by evicting another line).</li>
<li>P1 and P2 concurrently set the state of that line to a "pending" state, and issue a read request to the home node.</li>
<li>The home node receives the request from P1. Since the block is not cached anywhere, the memory directory will be in state HOME.</li>
<li>The home node sets its state to FRESH, its head pointer to 1, and replies to P1 with the data.</li>
<li>The home node receives P2's READ. Since the home node is in state FRESH, its data is up to date.</li>
<li>The home node sets its head pointer to 2 and replies to P2 with the data, and the "old" head pointer (P1).</li>
<li>P2 receives the data, but the action is not complete until it receives "permission" from P1 to become the new head of the list.</li>
<li>P2 remains in a pending state and sends a request to P1 to become the new head of the list.</li>
<li>P1 receives the request from P2, but is since it hasn't yet received the reply from the home directory it is still in a pending state.</li>
<li>P1 "extends" the pending list backwards. That is, P2 will be put at the head of the list, but in a "pending" state.</li>
<li>P1 receives the reply from the home directory and becomes the "true" head of the list. Even though P2 is ahead of P1 in the list, it's not the "true head," but a part of the "pending list."</li>
<li>P1 passes the "true head" status on to P2.</li>
</ul>

By maintaining a "pending list" and a "true head", read requests are atomic and we avoid the race condition sufferred under the SSCI protocol (albeit by adding more complexity). 

==== Example 2 ====

Suppose some block of data is being shared among several caches. Our linked list of sharers is P1-P2-P3-P4-P5. P3 needs to purge the line containing that block of data. 

Under the SSCI protocol, P3 will send an UpdPtr message to the processors represented by the previous and next pointers (P2 and P4 respectively). P2 will set its next pointer to P4, and P4 will set its next pointer to P2. 

Consider what might happen if P3 and P4 concurrently purge their lines of shared data.
<ul>
<li>P3 sends UpdPtr(P3->P2) and UpdPtr(P3->P4) and purges its data</li>
<li>Concurrently, P4 sends UpdPtr(P4->P3) and UpdPtr(P4->P5) and purges its data</li>
<li>P2 received the UpdPtr from P3 and sets its "next" pointer to P4</li>
<li>ERROR! P4 does not have the line cached!</li>
</ul>
Since P4 has already purged and is no longer in the list of sharers, we have a race condition. 
Now let's examine the same scenario under the SCI protocol. In the SCI protocol, a node that wants to "roll out" is put in a pending state until it receives acknowledgment from both the next and previous nodes. 
<ul>
<li>P3 and P4 both put themselves in a pending state.</li>
<li>P3 sends UpdPtr(P3->P2) and UpdPtr(P3->P4)</li>
<li>Concurrently, P4 sends UpdPtr(P4->P3) and UpdPtr(P4->P5)</li>
<li>Deadlock! Neither P3 nor P4 will respond to the other while in a pending state.</li>
<li>Resolution: the node nearer to the tail of the list (P4) is given priority.</li>
<li>P3 must wait until P4 completes its rollout, giving a shared list of P1-P2-P3-P5.</li>
<li>P3 rolls out.</li>
</ul>

So, pending states are necessary to preserve a correct representation of the shared list, but even then we must deal with deadlock resolution. 

=== Links ===

http://www.scizzl.com/WhatIsSCI.html 
http://www.lrr.in.tum.de/~gerndt/home/Teaching/scalable_shared_memory_systems/Kapitel8.pdf 
http://csdl2.computer.org/persagen/DLAbsToc.jsp?resourcePath=/dl/mags/mi/&toc=comp/mags/mi/1992/01/m1toc.xml&DOI=10.1109/40.124376 
http://www.hcs.ufl.edu/SCI_Internal/

CSC/ECE 506 Fall 2007/wiki3 2 aY3w

2007-10-17T21:19:01Z

Jfswaffo:

SCI. The IEEE Scalable Coherent Interface is a superset of the SSCI protocol we have been considering in class. A lot has been written about it, but it is still difficult to comprehend. Using SSCI as a starting point, explain why additional states are necessary, and give (or cite) examples that demonstrate how they work. Ideally, this would still be an overview of the working of the protocol, referencing more detailed documentation on the Web.

=== A Brief Overview of the SSCI Protocol ===

The Simple Scalable Coherence Interface (SSCI) protocol is a simplified version of the SCI protocol. While the SCI protocol has 29 stable states and many pending states, the SSCI protocol has only 3 states. Consequently, many race conditions are possible. Here we give a brief overview of the SSCI protocol, and elaborate on some possible race conditions in the final section. 
 
The caches themselves follow the MESI protocol, and thus are in one of those four states. Each block of cached data has a list of sharers, or processors that have that block cached. This list is represented as a doubly linked list that is distributed among the sharers themselves. 

In addition to the MESI state, each cache maintains a "next" pointer and a "previous" pointer. Each pointer points to another node in the list of sharers of the cached block of data. The head of the list will have a previous pointer value of 0, and the tail of the list will have a next pointer value of 0. 

Each block of data has a "home directory," located in some (possibly remote) memory location. The home directory is normally computable by the memory address of the block of data. If the block is cached, the home directory will contain the head pointer of the list of sharers. Additionally, the home directory will contain state information for the block.
As previously stated, in the SSCI protocol the memory directory is in one of three states. They are: 

<ul>
<li>UNOWNED - the block is unowned by any cache.</li>
<li>SHARED - the block is owned by multiple caches. Main memory is up to date.</li>
<li>EXCLUSIVE/MODIFIED - the (possibly dirty) block is owned by a single cache. Main memory is possibly out of date.</li>
</ul>

<hr>
=== A Brief Overview of the SCI Protocol ===

In this section we give a very brief overview of the SCI protocol. This is not meant to be a complete description, but to give enough information to illustrate some key differences in the SSCI and SCI protocols. 

==== Memory Directory States ====
Similar to the SSCI protocol, in SCI the memory directory is one of three states:
 
<ul>
<li>HOME - no remote cache contains a copy of the block.</li>
<li>FRESH - one of more remote caches may have a read-only copy of the block. Main memory is up to date.</li>
<li>GONE - the cache at the head of the sharing list contains an exclusive (possibly dirty) copy of the block.</li>
</ul>

==== Cache States ====
Additionally, each cache has a state, either stable or pending. Stable states have two parts: 
<ol>
<li>Where the cache entry is located in the sharing list for that block</li>
<ul>
<li>ONLY - singleton list</li>
<li>HEAD - head of sharing list of more than one node</li>
<li>MID - not head or tail of sharing list of more than one node</li>
<li>TAIL - tail of sharing list of more than one node</li>
</ul>
<li>State of the cached block</li>
<ul>
<li>DIRTY - modified and writable</li>
<li>CLEAN - unmodified and writable, same contents as memory</li>
<li>FRESH - data is readable and writable, but memory must be informed before memory is written</li>
<li>COPY - unmodified and readable</li>
<li>many others</li>
</ul>
</ol>

These two parts together describe the cache state, e.g. FRESH-ONLY or MID-VALID.

==== List Operations ====
SCI defines three primitive list operations for shared lists:
<ol>
<li>List construction - adding a new node to the head of the sharing list</li>
<li>Rollout - removing a node from the sharing list</li>
<li>Invalidation - invalidate all other sharers. Can only be performed by the head node.</li>
</ol>

The head of the list of sharers can be thought of as the owner. Only the head can modify the cached data. If some other sharer wants to modify the data, it must first rollout of the list and reattach as the head. 

<hr>
=== Why Additional States are Needed ===

The principle difference between SCI and SSCI is that SCI provides mechanisms for '''resolving race conditions''' and '''preserving serialization'''.

==== Example 1 ====
Suppose some processor, say P1, issues a read request and misses on some block that is not cached by any processor. So, the block will have to be fetched from main memory and the line will be put into P1's local cache. Space will have to be allocated in P1's cache, usually by evicting some other line. 

In the SSCI protocol, P1 will send a READ message to the home directory. The home directory will reply with the data and set its state to EM, and its head pointer to 1. Upon receipt, P1 will put the block in the allocated line, set its state to E (from the MESI protocol), and its next/previous pointers to 0. 

Consider what might happen if two processors both read miss concurrently. 
<ul>
<li>P1 sends a READ request to the home node.</li>
<li>Concurrently, P2 sends a READ request to the home node.</li>
<li>The home node receives the request from P1.</li>
<li>The home node sets its state to EM, its head pointer to 1 (P1), and sends the data to P1.</li>
<li>The home node receives the request from P2.</li>
<li>The home node sends a ReplyID to P2, informing it that P1 "owns" the data.</li>
<li>P2 receives the ReplyID and sends WB+Int+UpdPtr to P1.</li>
<li>P1 receives the message from P2</li>
<li>ERROR! P1 hasn't yet received the ReplyD from the home directory!</li>
</ul>

Due to network latency, it's possible that network messages are received "out of order," causing race conditions such as the one above.

Now let's consider the same scenario in SCI. 

<ul>
<li>P1 and P2 both read miss.</li>
<li>P1 and P2 set aside space for the line to be read in (possibly by evicting another line).</li>
<li>P1 and P2 concurrently set the state of that line to a "pending" state, and issue a read request to the home node.</li>
<li>The home node receives the request from P1. Since the block is not cached anywhere, the memory directory will be in state HOME.</li>
<li>The home node sets its state to FRESH, its head pointer to 1, and replies to P1 with the data.</li>
<li>The home node receives P2's READ. Since the home node is in state FRESH, its data is up to date.</li>
<li>The home node sets its head pointer to 2 and replies to P2 with the data, and the "old" head pointer (P1).</li>
<li>P2 receives the data, but the action is not complete until it receives "permission" from P1 to become the new head of the list.</li>
<li>P2 remains in a pending state and sends a request to P1 to become the new head of the list.</li>
<li>P1 receives the request from P2, but is since it hasn't yet received the reply from the home directory it is still in a pending state.</li>
<li>P1 "extends" the pending list backwards. That is, P2 will be put at the head of the list, but in a "pending" state.</li>
<li>P1 receives the reply from the home directory and becomes the "true" head of the list. Even though P2 is ahead of P1 in the list, it's not the "true head," but a part of the "pending list."</li>
<li>P1 passes the "true head" status on to P2.</li>
</ul>

By maintaining a "pending list" and a "true head", read requests are atomic and we avoid the race condition sufferred under the SSCI protocol (albeit by adding more complexity). 

==== Example 2 ====

Suppose some block of data is being shared among several caches. Our linked list of sharers is P1-P2-P3-P4-P5. P3 needs to purge the line containing that block of data. 

Under the SSCI protocol, P3 will send an UpdPtr message to the processors represented by the previous and next pointers (P2 and P4 respectively). P2 will set its next pointer to P4, and P4 will set its next pointer to P2. 

Consider what might happen if P3 and P4 concurrently purge their lines of shared data.
<ul>
<li>P3 sends UpdPtr(P3->P2) and UpdPtr(P3->P4) and purges its data</li>
<li>Concurrently, P4 sends UpdPtr(P4->P3) and UpdPtr(P4->P5) and purges its data</li>
<li>P2 received the UpdPtr from P3 and sets its "next" pointer to P4</li>
<li>ERROR! P4 does not have the line cached!</li>
</ul>
Since P4 has already purged and is no longer in the list of sharers, we have a race condition. 
Now let's examine the same scenario under the SCI protocol. In the SCI protocol, a node that wants to "roll out" is put in a pending state until it receives acknowledgment from both the next and previous nodes. 
<ul>
<li>P3 and P4 both put themselves in a pending state.</li>
<li>P3 sends UpdPtr(P3->P2) and UpdPtr(P3->P4)</li>
<li>Concurrently, P4 sends UpdPtr(P4->P3) and UpdPtr(P4->P5)</li>
<li>Deadlock! Neither P3 nor P4 will respond to the other while in a pending state.</li>
<li>Resolution: the node nearer to the tail of the list (P4) is given priority.</li>
<li>P3 must wait until P4 completes its rollout, giving a shared list of P1-P2-P3-P5.</li>
<li>P3 rolls out.</li>
</ul>

So, pending states are necessary to preserve a correct representation of the shared list, but even then we must deal with deadlock resolution. 

=== Links ===

http://www.scizzl.com/WhatIsSCI.html 
http://www.lrr.in.tum.de/~gerndt/home/Teaching/scalable_shared_memory_systems/Kapitel8.pdf 
http://csdl2.computer.org/persagen/DLAbsToc.jsp?resourcePath=/dl/mags/mi/&toc=comp/mags/mi/1992/01/m1toc.xml&DOI=10.1109/40.124376 
http://www.hcs.ufl.edu/SCI_Internal/

CSC/ECE 506 Fall 2007/wiki3 2 aY3w

2007-10-17T20:52:46Z

Jfswaffo:

SCI. The IEEE Scalable Coherent Interface is a superset of the SSCI protocol we have been considering in class. A lot has been written about it, but it is still difficult to comprehend. Using SSCI as a starting point, explain why additional states are necessary, and give (or cite) examples that demonstrate how they work. Ideally, this would still be an overview of the working of the protocol, referencing more detailed documentation on the Web.

=== A Brief Overview of the SSCI Protocol ===

The Simple Scalable Coherence Interface (SSCI) protocol is a simplified version of the SCI protocol. While the SCI protocol has 29 stable states and many pending states, the SSCI protocol has only 3 states. Consequently, many race conditions are possible. Here we give a brief overview of the SSCI protocol, and elaborate on some possible race conditions in the final section. 
 
The caches themselves follow the MESI protocol, and thus are in one of those four states. Each block of cached data has a list of sharers, or processors that have that block cached. This list is represented as a doubly linked list that is distributed among the sharers themselves. 

In addition to the MESI state, each cache maintains a "next" pointer and a "previous" pointer. Each pointer points to another node in the list of sharers of the cached block of data. The head of the list will have a previous pointer value of 0, and the tail of the list will have a next pointer value of 0. 

Each block of data has a "home directory," located in some (possibly remote) memory location. The home directory is normally computable by the memory address of the block of data. If the block is cached, the home directory will contain the head pointer of the list of sharers. Additionally, the home directory will contain state information for the block.
As previously stated, in the SSCI protocol the memory directory is in one of three states. They are: 

<ul>
<li>UNOWNED - the block is unowned by any cache.</li>
<li>SHARED - the block is owned by multiple caches. Main memory is up to date.</li>
<li>EXCLUSIVE/MODIFIED - the (possibly dirty) block is owned by a single cache. Main memory is possibly out of date.</li>
</ul>

<hr>
=== A Brief Overview of the SCI Protocol ===

In this section we give a very brief overview of the SCI protocol. This is not meant to be a complete description, but to give enough information to illustrate some key differences in the SSCI and SCI protocols. 

==== Memory Directory States ====
Similar to the SSCI protocol, in SCI the memory directory is one of three states:
 
<ul>
<li>HOME - no remote cache contains a copy of the block.</li>
<li>FRESH - one of more remote caches may have a read-only copy of the block. Main memory is up to date.</li>
<li>GONE - the cache at the head of the sharing list contains an exclusive (possibly dirty) copy of the block.</li>
</ul>

==== Cache States ====
Additionally, each cache has a state, either stable or pending. Stable states have two parts: 
<ol>
<li>Where the cache entry is located in the sharing list for that block</li>
<ul>
<li>ONLY - singleton list</li>
<li>HEAD - head of sharing list of more than one node</li>
<li>MID - not head or tail of sharing list of more than one node</li>
<li>TAIL - tail of sharing list of more than one node</li>
</ul>
<li>State of the cached block</li>
<ul>
<li>DIRTY - modified and writable</li>
<li>CLEAN - unmodified and writable, same contents as memory</li>
<li>FRESH - data is readable and writable, but memory must be informed before memory is written</li>
<li>COPY - unmodified and readable</li>
<li>many others</li>
</ul>
</ol>

These two parts together describe the cache state, e.g. FRESH-ONLY or MID-VALID.

==== List Operations ====
SCI defines three primitive list operations for shared lists:
<ol>
<li>List construction - adding a new node to the head of the sharing list</li>
<li>Rollout - removing a node from the sharing list</li>
<li>Invalidation - invalidate all other sharers. Can only be performed by the head node.</li>
</ol>

The head of the list of sharers can be thought of as the owner. Only the head can modify the cached data. If some other sharer wants to modify the data, it must first rollout of the list and reattach as the head. 

<hr>
=== Why Additional States are Needed ===

The principle difference between SCI and SSCI is that SCI provides mechanisms for '''resolving race conditions''' and '''preserving serialization'''.

==== Example 1 ====
Suppose some processor, say P1, issues a read request and misses on some block that is not cached by any processor. So, the block will have to be fetched from main memory (or possibly some remote cache), and the line will be put into P1's local cache. Space will have to be allocated in P1's cache, usually by evicting some other line. 

In the SSCI protocol, P1 will send a READ message to the home directory. The home directory will reply with the data and set its state to EM, and its head pointer to 1. Upon receipt, P1 will put the block in the allocated line, set its state to E (from the MESI protocol), and its next/previous pointers to 0. 

Consider what might happen if two processors both read miss concurrently. 
<ul>
<li>P1 sends a READ request to the home node.</li>
<li>Concurrently, P2 sends a READ request to the home node.</li>
<li>The home node receives the request from P1.</li>
<li>The home node sets its state to EM, its head pointer to 1 (P1), and sends the data to P1.</li>
<li>The home node receives the request from P2.</li>
<li>The home node sends a ReplyID to P2, informing it that P1 "owns" the data.</li>
<li>P2 receives the ReplyID and sends WB+Int+UpdPtr to P1.</li>
<li>P1 receives the message from P2</li>
<li>ERROR! P1 hasn't yet received the ReplyD from the home directory!</li>
</ul>

Due to network latency, it's possible that network messages are received "out of order," causing race conditions such as the one above.

Now let's consider the same scenario in SCI. 

<ul>
<li>P1 and P2 both read miss.</li>
<li>P1 and P2 set aside space for the line to be read in (possibly by evicting another line).</li>
<li>P1 and P2 concurrently set the state of that line to a "pending" state, and issue a read request to the home node.</li>
<li>The home node receives the request from P1. Since the block is not cached anywhere, the memory directory will be in state HOME.</li>
<li>The home node sets its state to FRESH, its head pointer to 1, and replies to P1 with the data.</li>
<li>The home node receives P2's READ. Since the home node is in state FRESH, its data is up to date.</li>
<li>The home node sets its head pointer to 2 and replies to P2 with the data, and the "old" head pointer (P1).</li>
<li>P2 receives the data, but the action is not complete until it receives "permission" from P1 to become the new head of the list.</li>
<li>P2 remains in a pending state and sends a request to P1 to become the new head of the list.</li>
<li>P1 receives the request from P2, but is since it hasn't yet received the reply from the home directory it is still in a pending state.</li>
<li>P1 "extends" the pending list backwards. That is, P2 will be put at the head of the list, but in a "pending" state.</li>
<li>P1 receives the reply from the home directory and becomes the "true" head of the list. Even though P2 is ahead of P1 in the list, it's not the "true head," but a part of the "pending list."</li>
<li>P1 passes the "true head" status on to P2.</li>
</ul>

By maintaining a "pending list" and a "true head", read requests are atomic and we avoid the race condition sufferred under the SSCI protocol (albeit by adding more complexity). 

==== Example 2 ====

Suppose some block of data is being shared among several caches. Our linked list of sharers is P1-P2-P3-P4-P5. P3 needs to purge the line containing that block of data. 

Under the SSCI protocol, P3 will send an UpdPtr message to the processors represented by the previous and next pointers (P2 and P4 respectively). P2 will set its next pointer to P4, and P4 will set its next pointer to P2. 

Consider what might happen if P3 and P4 concurrently purge their lines of shared data.
<ul>
<li>P3 sends UpdPtr(P3->P2) and UpdPtr(P3->P4) and purges its data</li>
<li>Concurrently, P4 sends UpdPtr(P4->P3) and UpdPtr(P4->P5) and purges its data</li>
<li>P2 received the UpdPtr from P3 and sets its "next" pointer to P4</li>
<li>ERROR! P4 does not have the line cached!</li>
</ul>
Since P4 has already purged and is no longer in the list of sharers, we have a race condition. 
Now let's examine the same scenario under the SCI protocol. In the SCI protocol, a node that wants to "roll out" is put in a pending state until it receives acknowledgment from both the next and previous nodes. 
<ul>
<li>P3 and P4 both put themselves in a pending state.</li>
<li>P3 sends UpdPtr(P3->P2) and UpdPtr(P3->P4)</li>
<li>Concurrently, P4 sends UpdPtr(P4->P3) and UpdPtr(P4->P5)</li>
<li>Deadlock! Neither P3 nor P4 will respond to the other while in a pending state.</li>
<li>Resolution: the node nearer to the tail of the list (P4) is given priority.</li>
<li>P3 must wait until P4 completes its rollout, giving a shared list of P1-P2-P3-P5.</li>
<li>P3 rolls out.</li>
</ul>

So, pending states are necessary to preserve a correct representation of the shared list, but even then we must deal with deadlock resolution. 

=== Links ===

http://www.scizzl.com/WhatIsSCI.html 
http://www.lrr.in.tum.de/~gerndt/home/Teaching/scalable_shared_memory_systems/Kapitel8.pdf 
http://csdl2.computer.org/persagen/DLAbsToc.jsp?resourcePath=/dl/mags/mi/&toc=comp/mags/mi/1992/01/m1toc.xml&DOI=10.1109/40.124376 
http://www.hcs.ufl.edu/SCI_Internal/

CSC/ECE 506 Fall 2007/wiki3 2 aY3w

2007-10-17T17:41:04Z

Jfswaffo:

SCI. The IEEE Scalable Coherent Interface is a superset of the SSCI protocol we have been considering in class. A lot has been written about it, but it is still difficult to comprehend. Using SSCI as a starting point, explain why additional states are necessary, and give (or cite) examples that demonstrate how they work. Ideally, this would still be an overview of the working of the protocol, referencing more detailed documentation on the Web.

=== A Brief Overview of the SSCI Protocol ===

The Simple Scalable Coherence Interface (SSCI) protocol is a simplified version of the SCI protocol. While the SCI protocol has 29 stable states and many pending states, the SSCI protocol has only 3 states. Consequently, many race conditions are possible. Here we give a brief overview of the SSCI protocol, and elaborate on the possible race conditions in the final section.

As previously states, in the SSCI protocol the memory directory is in one of three states. They are:
 
<ul>
<li>UNOWNED - the block is unowned by any cache.</li>
<li>SHARED - the block is owned by multiple caches. Main memory is up to date.</li>
<li>EXCLUSIVE/MODIFIED - the (possibly dirty) block is owned by a single cache. Main memory is possibly out of date.</li>
</ul>
<hr>
=== A Brief Overview of the SCI Protocol ===

==== Memory Directory States ====
Similar to the SSCI protocol, in SCI the memory directory is one of three states:
 
<ul>
<li>HOME - no remote cache contains a copy of the block.</li>
<li>FRESH - one of more remote caches may have a read-only copy of the block. Main memory is up to date.</li>
<li>GONE - the cache at the head of the sharing list contains an exclusive (possibly dirty) copy of the block.</li>
</ul>

==== Cache States ====
Additionally, each cache has a state, either stable or pending. Stable states have two parts: 
<ol>
<li>Where the cache entry is located in the sharing list for that block</li>
<ul>
<li>ONLY - singleton list</li>
<li>HEAD - head of sharing list of more than one node</li>
<li>MID - not head or tail of sharing list of more than one node</li>
<li>TAIL - tail of sharing list of more than one node</li>
</ul>
<li>State of the cached block</li>
<ul>
<li>DIRTY - modified and writable</li>
<li>CLEAN - unmodified and writable, same contents as memory</li>
<li>FRESH - data is readable and writable, but memory must be informed before memory is written</li>
<li>COPY - unmodified and readable</li>
<li>many others</li>
</ul>
</ol>

These two parts together describe the cache state, e.g. FRESH-ONLY or MID-VALID.

==== List Operations ====
SCI defines three primitive list operations for shared lists:
<ol>
<li>List construction - adding a new node to the head of the sharing list</li>
<li>Rollout - removing a node from the sharing list</li>
<li>Invalidation - invalidate all other sharers. Can only be performed by the head node.</li>
</ol>

<hr>
=== Why Additional States are Needed ===

The principle difference between SCI and SSCI is that SCI provides mechanisms for '''resolving race conditions''' and '''preserving serialization'''.

==== Example 1 ====
Suppose some processor, say P1, issues a read request and misses on some block that is not cached by any processor. So, the block will have to be fetched from main memory (or possibly some remote cache), and the line will be put into P1's local cache. Space will have to be allocated in P1's cache, usually by evicting some other line. 

In the SSCI protocol, P1 will send a READ message to the home directory. The home directory will reply with the data and set its state to EM, and its head pointer to 1. Upon receipt, P1 will put the block in the allocated line, set its state to E (from the MESI protocol), and its next/previous pointers to 0. 

Consider what might happen if two processors both read miss concurrently. 
<ul>
<li>P1 sends a READ request to the home node.</li>
<li>Concurrently, P2 sends a READ request to the home node.</li>
<li>The home node receives the request from P1.</li>
<li>The home node sets its state to EM, its head pointer to 1 (P1), and sends the data to P1.</li>
<li>The home node receives the request from P2.</li>
<li>The home node sends a ReplyID to P2, informing it that P1 "owns" the data.</li>
<li>P2 receives the ReplyID and sends WB+Int+UpdPtr to P1.</li>
<li>P1 receives the message from P2</li>
<li>ERROR! P1 hasn't yet received the ReplyD from the home directory!</li>
</ul>

Due to network latency, it's possible that network messages are received "out of order," causing race conditions such as the one above.

Now let's consider the same scenario in SCI. 

<ul>
<li>P1 and P2 both read miss.</li>
<li>P1 and P2 set aside space for the line to be read in (possibly by evicting another line).</li>
<li>P1 and P2 concurrently set the state of that line to a "pending" state, and issue a read request to the home node.</li>
<li>The home node receives the request from P1. Since the block is not cached anywhere, the memory directory will be in state HOME.</li>
<li>The home node sets its state to FRESH, its head pointer to 1, and replies to P1 with the data.</li>
<li>The home node receives P2's READ. Since the home node is in state FRESH, its data is up to date.</li>
<li>The home node sets its head pointer to 2 and replies to P2 with the data, and the "old" head pointer (P1).</li>
<li>P2 receives the data, but the action is not complete until it receives "permission" from P1 to become the new head of the list.</li>
<li>P2 remains in a pending state and sends a request to P1 to become the new head of the list.</li>
<li>P1 receives the request from P2, but is since it hasn't yet received the reply from the home directory it is still in a pending state.</li>
<li>P1 "extends" the pending list backwards. That is, P2 will be put at the head of the list, but in a "pending" state.</li>
<li>P1 receives the reply from the home directory and becomes the "true" head of the list. Even though P2 is ahead of P1 in the list, it's not the "true head," but a part of the "pending list."</li>
<li>P1 passes the "true head" status on to P2.</li>
</ul>

By maintaining a "pending list" and a "true head", read requests are atomic and we avoid the race condition sufferred under the SSCI protocol (albeit by adding more complexity). 

==== Example 2 ====

Suppose some block of data is being shared among several caches. Our linked list of sharers is P1-P2-P3-P4-P5. P3 needs to purge the line containing that block of data. 

Under the SSCI protocol, P3 will send an UpdPtr message to the processors represented by the previous and next pointers (P2 and P4 respectively). P2 will set its next pointer to P4, and P4 will set its next pointer to P2. 

Consider what might happen if P3 and P4 concurrently purge their lines of shared data.
<ul>
<li>P3 sends UpdPtr(P3->P2) and UpdPtr(P3->P4) and purges its data</li>
<li>Concurrently, P4 sends UpdPtr(P4->P3) and UpdPtr(P4->P5) and purges its data</li>
<li>P2 received the UpdPtr from P3 and sets its "next" pointer to P4</li>
<li>ERROR! P4 does not have the line cached!</li>
</ul>
Since P4 has already purged and is no longer in the list of sharers, we have a race condition. 
Now let's examine the same scenario under the SCI protocol. In the SCI protocol, a node that wants to "roll out" is put in a pending state until it receives acknowledgment from both the next and previous nodes. 
<ul>
<li>P3 and P4 both put themselves in a pending state.</li>
<li>P3 sends UpdPtr(P3->P2) and UpdPtr(P3->P4)</li>
<li>Concurrently, P4 sends UpdPtr(P4->P3) and UpdPtr(P4->P5)</li>
<li>Deadlock! Neither P3 nor P4 will respond to the other while in a pending state.</li>
<li>Resolution: the node nearer to the tail of the list (P4) is given priority.</li>
<li>P3 must wait until P4 completes its rollout, giving a shared list of P1-P2-P3-P5.</li>
<li>P3 rolls out.</li>
</ul>

So, pending states are necessary to preserve a correct representation of the shared list, but even then we must deal with deadlock resolution. 

=== Links ===

http://www.scizzl.com/WhatIsSCI.html 
http://www.lrr.in.tum.de/~gerndt/home/Teaching/scalable_shared_memory_systems/Kapitel8.pdf

CSC/ECE 506 Fall 2007/wiki3 2 aY3w

2007-10-17T17:40:37Z

Jfswaffo:

SCI. The IEEE Scalable Coherent Interface is a superset of the SSCI protocol we have been considering in class. A lot has been written about it, but it is still difficult to comprehend. Using SSCI as a starting point, explain why additional states are necessary, and give (or cite) examples that demonstrate how they work. Ideally, this would still be an overview of the working of the protocol, referencing more detailed documentation on the Web.

=== A Brief Overview of the SSCI Protocol ===

The Simple Scalable Coherence Interface (SSCI) protocol is a simplified version of the SCI protocol. While the SCI protocol has 29 stable states and many pending states, the SSCI protocol has only 3 states. Consequently, many race conditions are possible. Here we give a brief overview of the SSCI protocol, and elaborate on the possible race conditions in the final section.

As previously states, in the SSCI protocol the memory directory is in one of three states. They are:
 
<ul>
<li>UNOWNED - the block is unowned by any cache.</li>
<li>SHARED - the block is owned by multiple caches. Main memory is up to date.</li>
<li>EXCLUSIVE/MODIFIED - the (possibly dirty) block is owned by a single cache. Main memory is possibly out of date.</li>
</ul>
<hr>
=== A Brief Overview of the SCI Protocol ===

<hr>
==== Memory Directory States ====
Similar to the SSCI protocol, in SCI the memory directory is one of three states:
 
<ul>
<li>HOME - no remote cache contains a copy of the block.</li>
<li>FRESH - one of more remote caches may have a read-only copy of the block. Main memory is up to date.</li>
<li>GONE - the cache at the head of the sharing list contains an exclusive (possibly dirty) copy of the block.</li>
</ul>

==== Cache States ====
Additionally, each cache has a state, either stable or pending. Stable states have two parts: 
<ol>
<li>Where the cache entry is located in the sharing list for that block</li>
<ul>
<li>ONLY - singleton list</li>
<li>HEAD - head of sharing list of more than one node</li>
<li>MID - not head or tail of sharing list of more than one node</li>
<li>TAIL - tail of sharing list of more than one node</li>
</ul>
<li>State of the cached block</li>
<ul>
<li>DIRTY - modified and writable</li>
<li>CLEAN - unmodified and writable, same contents as memory</li>
<li>FRESH - data is readable and writable, but memory must be informed before memory is written</li>
<li>COPY - unmodified and readable</li>
<li>many others</li>
</ul>
</ol>

These two parts together describe the cache state, e.g. FRESH-ONLY or MID-VALID.

==== List Operations ====
SCI defines three primitive list operations for shared lists:
<ol>
<li>List construction - adding a new node to the head of the sharing list</li>
<li>Rollout - removing a node from the sharing list</li>
<li>Invalidation - invalidate all other sharers. Can only be performed by the head node.</li>
</ol>

<hr>
=== Why Additional States are Needed ===

The principle difference between SCI and SSCI is that SCI provides mechanisms for '''resolving race conditions''' and '''preserving serialization'''.

==== Example 1 ====
Suppose some processor, say P1, issues a read request and misses on some block that is not cached by any processor. So, the block will have to be fetched from main memory (or possibly some remote cache), and the line will be put into P1's local cache. Space will have to be allocated in P1's cache, usually by evicting some other line. 

In the SSCI protocol, P1 will send a READ message to the home directory. The home directory will reply with the data and set its state to EM, and its head pointer to 1. Upon receipt, P1 will put the block in the allocated line, set its state to E (from the MESI protocol), and its next/previous pointers to 0. 

Consider what might happen if two processors both read miss concurrently. 
<ul>
<li>P1 sends a READ request to the home node.</li>
<li>Concurrently, P2 sends a READ request to the home node.</li>
<li>The home node receives the request from P1.</li>
<li>The home node sets its state to EM, its head pointer to 1 (P1), and sends the data to P1.</li>
<li>The home node receives the request from P2.</li>
<li>The home node sends a ReplyID to P2, informing it that P1 "owns" the data.</li>
<li>P2 receives the ReplyID and sends WB+Int+UpdPtr to P1.</li>
<li>P1 receives the message from P2</li>
<li>ERROR! P1 hasn't yet received the ReplyD from the home directory!</li>
</ul>

Due to network latency, it's possible that network messages are received "out of order," causing race conditions such as the one above.

Now let's consider the same scenario in SCI. 

<ul>
<li>P1 and P2 both read miss.</li>
<li>P1 and P2 set aside space for the line to be read in (possibly by evicting another line).</li>
<li>P1 and P2 concurrently set the state of that line to a "pending" state, and issue a read request to the home node.</li>
<li>The home node receives the request from P1. Since the block is not cached anywhere, the memory directory will be in state HOME.</li>
<li>The home node sets its state to FRESH, its head pointer to 1, and replies to P1 with the data.</li>
<li>The home node receives P2's READ. Since the home node is in state FRESH, its data is up to date.</li>
<li>The home node sets its head pointer to 2 and replies to P2 with the data, and the "old" head pointer (P1).</li>
<li>P2 receives the data, but the action is not complete until it receives "permission" from P1 to become the new head of the list.</li>
<li>P2 remains in a pending state and sends a request to P1 to become the new head of the list.</li>
<li>P1 receives the request from P2, but is since it hasn't yet received the reply from the home directory it is still in a pending state.</li>
<li>P1 "extends" the pending list backwards. That is, P2 will be put at the head of the list, but in a "pending" state.</li>
<li>P1 receives the reply from the home directory and becomes the "true" head of the list. Even though P2 is ahead of P1 in the list, it's not the "true head," but a part of the "pending list."</li>
<li>P1 passes the "true head" status on to P2.</li>
</ul>

By maintaining a "pending list" and a "true head", read requests are atomic and we avoid the race condition sufferred under the SSCI protocol (albeit by adding more complexity). 

==== Example 2 ====

Suppose some block of data is being shared among several caches. Our linked list of sharers is P1-P2-P3-P4-P5. P3 needs to purge the line containing that block of data. 

Under the SSCI protocol, P3 will send an UpdPtr message to the processors represented by the previous and next pointers (P2 and P4 respectively). P2 will set its next pointer to P4, and P4 will set its next pointer to P2. 

Consider what might happen if P3 and P4 concurrently purge their lines of shared data.
<ul>
<li>P3 sends UpdPtr(P3->P2) and UpdPtr(P3->P4) and purges its data</li>
<li>Concurrently, P4 sends UpdPtr(P4->P3) and UpdPtr(P4->P5) and purges its data</li>
<li>P2 received the UpdPtr from P3 and sets its "next" pointer to P4</li>
<li>ERROR! P4 does not have the line cached!</li>
</ul>
Since P4 has already purged and is no longer in the list of sharers, we have a race condition. 
Now let's examine the same scenario under the SCI protocol. In the SCI protocol, a node that wants to "roll out" is put in a pending state until it receives acknowledgment from both the next and previous nodes. 
<ul>
<li>P3 and P4 both put themselves in a pending state.</li>
<li>P3 sends UpdPtr(P3->P2) and UpdPtr(P3->P4)</li>
<li>Concurrently, P4 sends UpdPtr(P4->P3) and UpdPtr(P4->P5)</li>
<li>Deadlock! Neither P3 nor P4 will respond to the other while in a pending state.</li>
<li>Resolution: the node nearer to the tail of the list (P4) is given priority.</li>
<li>P3 must wait until P4 completes its rollout, giving a shared list of P1-P2-P3-P5.</li>
<li>P3 rolls out.</li>
</ul>

So, pending states are necessary to preserve a correct representation of the shared list, but even then we must deal with deadlock resolution. 

=== Links ===

http://www.scizzl.com/WhatIsSCI.html 
http://www.lrr.in.tum.de/~gerndt/home/Teaching/scalable_shared_memory_systems/Kapitel8.pdf

CSC/ECE 506 Fall 2007/wiki3 2 aY3w

2007-10-17T17:35:21Z

Jfswaffo:

SCI. The IEEE Scalable Coherent Interface is a superset of the SSCI protocol we have been considering in class. A lot has been written about it, but it is still difficult to comprehend. Using SSCI as a starting point, explain why additional states are necessary, and give (or cite) examples that demonstrate how they work. Ideally, this would still be an overview of the working of the protocol, referencing more detailed documentation on the Web.

=== A Brief Overview of the SSCI Protocol ===

The Simple Scalable Coherence Interface (SSCI) protocol is a simplified version of the SCI protocol. While the SCI protocol has 29 stable states and many pending states, the SSCI protocol has only 3 states. Consequently, many race conditions are possible. Here we give a brief overview of the SSCI protocol, and elaborate on the possible race conditions in the final section.

As previously states, in the SSCI protocol the memory directory is in one of three states. They are:
 
<ul>
<li>UNOWNED - the block is unowned by any cache.</li>
<li>SHARED - the block is owned by multiple caches. Main memory is up to date.</li>
<li>EXCLUSIVE/MODIFIED - the (possibly dirty) block is owned by a single cache. Main memory is possibly out of date.</li>
</ul>

=== A Brief Overview of the SCI Protocol ===

==== Memory Directory States ====
Similar to the SSCI protocol, in SCI the memory directory is one of three states:
 
<ul>
<li>HOME - no remote cache contains a copy of the block.</li>
<li>FRESH - one of more remote caches may have a read-only copy of the block. Main memory is up to date.</li>
<li>GONE - the cache at the head of the sharing list contains an exclusive (possibly dirty) copy of the block.</li>
</ul>

==== Cache States ====
Additionally, each cache has a state, either stable or pending. Stable states have two parts: 
<ol>
<li>Where the cache entry is located in the sharing list for that block</li>
<ul>
<li>ONLY - singleton list</li>
<li>HEAD - head of sharing list of more than one node</li>
<li>MID - not head or tail of sharing list of more than one node</li>
<li>TAIL - tail of sharing list of more than one node</li>
</ul>
<li>State of the cached block</li>
<ul>
<li>DIRTY - modified and writable</li>
<li>CLEAN - unmodified and writable, same contents as memory</li>
<li>FRESH - data is readable and writable, but memory must be informed before memory is written</li>
<li>COPY - unmodified and readable</li>
<li>many others</li>
</ul>
</ol>

These two parts together describe the cache state, e.g. FRESH-ONLY or MID-VALID.

==== List Operations ====
SCI defines three primitive list operations for shared lists:
<ol>
<li>List construction - adding a new node to the head of the sharing list</li>
<li>Rollout - removing a node from the sharing list</li>
<li>Invalidation - invalidate all other sharers. Can only be performed by the head node.</li>
</ol>

=== Why Additional States are Needed ===

The principle difference between SCI and SSCI is that SCI provides mechanisms for '''resolving race conditions''' and '''preserving serialization'''.

==== Example 1 ====
Suppose some processor, say P1, issues a read request and misses on some block that is not cached by any processor. So, the block will have to be fetched from main memory (or possibly some remote cache), and the line will be put into P1's local cache. Space will have to be allocated in P1's cache, usually by evicting some other line. 

In the SSCI protocol, P1 will send a READ message to the home directory. The home directory will reply with the data and set its state to EM, and its head pointer to 1. Upon receipt, P1 will put the block in the allocated line, set its state to E (from the MESI protocol), and its next/previous pointers to 0. 

Consider what might happen if two processors both read miss concurrently. 
<ul>
<li>P1 sends a READ request to the home node.</li>
<li>Concurrently, P2 sends a READ request to the home node.</li>
<li>The home node receives the request from P1.</li>
<li>The home node sets its state to EM, its head pointer to 1 (P1), and sends the data to P1.</li>
<li>The home node receives the request from P2.</li>
<li>The home node sends a ReplyID to P2, informing it that P1 "owns" the data.</li>
<li>P2 receives the ReplyID and sends WB+Int+UpdPtr to P1.</li>
<li>P1 receives the message from P2</li>
<li>ERROR! P1 hasn't yet received the ReplyD from the home directory!</li>
</ul>

Due to network latency, it's possible that network messages are received "out of order," causing race conditions such as the one above.

Now let's consider the same scenario in SCI. 

<ul>
<li>P1 and P2 both read miss.</li>
<li>P1 and P2 set aside space for the line to be read in (possibly by evicting another line).</li>
<li>P1 and P2 concurrently set the state of that line to a "pending" state, and issue a read request to the home node.</li>
<li>The home node receives the request from P1. Since the block is not cached anywhere, the memory directory will be in state HOME.</li>
<li>The home node sets its state to FRESH, its head pointer to 1, and replies to P1 with the data.</li>
<li>The home node receives P2's READ. Since the home node is in state FRESH, its data is up to date.</li>
<li>The home node sets its head pointer to 2 and replies to P2 with the data, and the "old" head pointer (P1).</li>
<li>P2 receives the data, but the action is not complete until it receives "permission" from P1 to become the new head of the list.</li>
<li>P2 remains in a pending state and sends a request to P1 to become the new head of the list.</li>
<li>P1 receives the request from P2, but is since it hasn't yet received the reply from the home directory it is still in a pending state.</li>
<li>P1 "extends" the pending list backwards. That is, P2 will be put at the head of the list, but in a "pending" state.</li>
<li>P1 receives the reply from the home directory and becomes the "true" head of the list. Even though P2 is ahead of P1 in the list, it's not the "true head," but a part of the "pending list."</li>
<li>P1 passes the "true head" status on to P2.</li>
</ul>

By maintaining a "pending list" and a "true head", read requests are atomic and we avoid the race condition sufferred under the SSCI protocol (albeit by adding more complexity). 

==== Example 2 ====

Suppose some block of data is being shared among several caches. Our linked list of sharers is P1-P2-P3-P4-P5. P3 needs to purge the line containing that block of data. 

Under the SSCI protocol, P3 will send an UpdPtr message to the processors represented by the previous and next pointers (P2 and P4 respectively). P2 will set its next pointer to P4, and P4 will set its next pointer to P2. 

Consider what might happen if P3 and P4 concurrently purge their lines of shared data.
<ul>
<li>P3 sends UpdPtr(P3->P2) and UpdPtr(P3->P4) and purges its data</li>
<li>Concurrently, P4 sends UpdPtr(P4->P3) and UpdPtr(P4->P5) and purges its data</li>
<li>P2 received the UpdPtr from P3 and sets its "next" pointer to P4</li>
<li>ERROR! P4 does not have the line cached!</li>
</ul>
Since P4 has already purged and is no longer in the list of sharers, we have a race condition. 
Now let's examine the same scenario under the SCI protocol. In the SCI protocol, a node that wants to "roll out" is put in a pending state until it receives acknowledgment from both the next and previous nodes. 
<ul>
<li>P3 and P4 both put themselves in a pending state.</li>
<li>P3 sends UpdPtr(P3->P2) and UpdPtr(P3->P4)</li>
<li>Concurrently, P4 sends UpdPtr(P4->P3) and UpdPtr(P4->P5)</li>
<li>Deadlock! Neither P3 nor P4 will respond to the other while in a pending state.</li>
<li>Resolution: the node nearer to the tail of the list (P4) is given priority.</li>
<li>P3 must wait until P4 completes its rollout, giving a shared list of P1-P2-P3-P5.</li>
<li>P3 rolls out.</li>
</ul>

So, pending states are necessary to preserve a correct representation of the shared list, but even then we must deal with deadlock resolution. 

=== Links ===

http://www.scizzl.com/WhatIsSCI.html 
http://www.lrr.in.tum.de/~gerndt/home/Teaching/scalable_shared_memory_systems/Kapitel8.pdf

CSC/ECE 506 Fall 2007/wiki3 2 aY3w

2007-10-17T17:25:22Z

Jfswaffo:

SCI. The IEEE Scalable Coherent Interface is a superset of the SSCI protocol we have been considering in class. A lot has been written about it, but it is still difficult to comprehend. Using SSCI as a starting point, explain why additional states are necessary, and give (or cite) examples that demonstrate how they work. Ideally, this would still be an overview of the working of the protocol, referencing more detailed documentation on the Web.

=== A Brief Overview of the SSCI Protocol ===

The Simple Scalable Coherence Interface (SSCI) protocol is a simplified version of the SCI protocol. While the SCI protocol has 29 stable states and many pending states, the SSCI protocol has only 3 states. Consequently, many race conditions are possible. Here we give a brief overview of the SSCI protocol, and elaborate on the possible race conditions in the final section.

As previously states, in the SSCI protocol the memory directory is in one of three states. They are:
 
<ul>
<li>UNOWNED - the block is unowned by any cache.</li>
<li>SHARED - the block is owned by multiple caches. Main memory is up to date.</li>
<li>EXCLUSIVE/MODIFIED - the (possibly dirty) block is owned by a single cache. Main memory is possibly out of date.</li>
</ul>

=== A Brief Overview of the SCI Protocol ===

==== Memory Directory States ====
Similar to the SSCI protocol, in SCI the memory directory is one of three states:
 
<ul>
<li>HOME - no remote cache contains a copy of the block.</li>
<li>FRESH - one of more remote caches may have a read-only copy of the block. Main memory is up to date.</li>
<li>GONE - the cache at the head of the sharing list contains an exclusive (possibly dirty) copy of the block.</li>
</ul>

==== Cache States ====
Additionally, each cache has a state, either stable or pending. Stable states have two parts: 
<ol>
<li>Where the cache entry is located in the sharing list for that block</li>
<ul>
<li>ONLY - singleton list</li>
<li>HEAD - head of sharing list of more than one node</li>
<li>MID - not head or tail of sharing list of more than one node</li>
<li>TAIL - tail of sharing list of more than one node</li>
</ul>
<li>State of the cached block</li>
<ul>
<li>DIRTY - modified and writable</li>
<li>CLEAN - unmodified and writable, same contents as memory</li>
<li>FRESH - data is readable and writable, but memory must be informed before memory is written</li>
<li>COPY - unmodified and readable</li>
<li>many others</li>
</ul>
</ol>

These two parts together describe the cache state, e.g. FRESH-ONLY or MID-VALID.

==== List Operations ====
SCI defines three primitive list operations for shared lists:
<ol>
<li>List construction - adding a new node to the head of the sharing list</li>
<li>Rollout - removing a node from the sharing list</li>
<li>Invalidation - invalidate all other sharers. Can only be performed by the head node.</li>
</ol>

=== Why Additional States are Needed ===

The principle difference between SCI and SSCI is that SCI provides mechanisms for '''resolving race conditions''' and '''preserving serialization'''.

==== Example 1 ====
Suppose some processor, say P1, issues a read request and misses on some block that is not cached by any processor. So, the block will have to be fetched from main memory (or possibly some remote cache), and the line will be put into P1's local cache. Space will have to be allocated in P1's cache, usually by evicting some other line. 

In the SSCI protocol, P1 will send a READ message to the home directory. The home directory will reply with the data and set its state to EM, and its head pointer to 1. Upon receipt, P1 will put the block in the allocated line, set its state to E (from the MESI protocol), and its next/previous pointers to 0. 

Consider what might happen if two processors both read miss concurrently. 
<ul>
<li>P1 sends a READ request to the home node.</li>
<li>Concurrently, P2 sends a READ request to the home node.</li>
<li>The home node receives the request from P1.</li>
<li>The home node sets its state to EM, its head pointer to 1 (P1), and sends the data to P1.</li>
<li>The home node receives the request from P2.</li>
<li>The home node sends a ReplyID to P2, informing it that P1 "owns" the data.</li>
<li>P2 receives the ReplyID and sends WB+Int+UpdPtr to P1.</li>
<li>P1 receives the message from P2</li>
<li>ERROR! P1 hasn't yet received the ReplyD from the home directory!</li>
</ul>

Due to network latency, it's possible that network messages are received "out of order," causing race conditions such as the one above.

Now let's consider the same scenario in SCI. 

P1 and P2 both read miss. Both set aside space for the line to be read in, set the state of that line to a "pending" state, and issue the read request to the home node. When the home node receives the request from P1, the memory directory will be in state HOME (since the block is not cached anywhere). It will set its state to FRESH, set its head pointer to 1, and reply with the data. 

Now P2's request is processed by the home node. Since the home node is in state FRESH, its data is up to date. It sets its head pointer to 2 and replies to P2 with the data, and the "old" head pointer (P1). 

P2 receives the data, but the action is not complete until it receives "permission" from P1 to become the new head of the list. So, P2 remains in a pending state and sends a request to P1 to become the new head of the list. Recall that in our scenario, due to network latency, P1 still hasn't received the initial response from the home directory; P1 is still in a pending state. Under the SCI protocol, if a processor is in a pending state when it receives a list operation request (such as becoming the new head of the list), it will extend the pending list backwards. That is, P2 will be put at the head of the list, but in a "pending" state. When P1 completes its operation and becomes the "true" head of the list, it can then pass the "true head" status on to P2. In this way, read requests are atomic and we avoid the race condition sufferred under the SSCI protocol (albeit by adding more complexity). 

==== Example 2 ====

Suppose some block of data is being shared among several caches. Our linked list of sharers is P1-P2-P3-P4-P5. P3 needs to purge the line containing that block of data. 

Under the SSCI protocol, P3 will send an UpdPtr message to the processors represented by the previous and next pointers (P2 and P4 respectively). P2 will set its next pointer to P4, and P4 will set its next pointer to P2. 

Consider what might happen if P3 and P4 concurrently purge their lines of shared data.
<ul>
<li>P3 sends UpdPtr(P3->P2) and UpdPtr(P3->P4) and purges its data</li>
<li>Concurrently, P4 sends UpdPtr(P4->P3) and UpdPtr(P4->P5) and purges its data</li>
<li>P2 received the UpdPtr from P3 and sets its "next" pointer to P4</li>
<li>ERROR! P4 does not have the line cached!</li>
</ul>
Since P4 has already purged and is no longer in the list of sharers, we have a race condition. 
Now let's examine the same scenario under the SCI protocol. In the SCI protocol, a node that wants to "roll out" is put in a pending state until it receives acknowledgment from both the next and previous nodes. 
<ul>
<li>P3 and P4 both put themselves in a pending state.</li>
<li>P3 sends UpdPtr(P3->P2) and UpdPtr(P3->P4)</li>
<li>Concurrently, P4 sends UpdPtr(P4->P3) and UpdPtr(P4->P5)</li>
<li>Deadlock! Neither P3 nor P4 will respond to the other while in a pending state.</li>
<li>Resolution: the node nearer to the tail of the list (P4) is given priority.</li>
<li>P3 must wait until P4 completes its rollout, giving a shared list of P1-P2-P3-P5.</li>
<li>P3 rolls out.</li>
</ul>

So, pending states are necessary to preserve a correct representation of the shared list, but even then we must deal with deadlock resolution. 

=== Links ===

http://www.scizzl.com/WhatIsSCI.html 
http://www.lrr.in.tum.de/~gerndt/home/Teaching/scalable_shared_memory_systems/Kapitel8.pdf

CSC/ECE 506 Fall 2007/wiki3 2 aY3w

2007-10-17T16:17:59Z

Jfswaffo:

SCI. The IEEE Scalable Coherent Interface is a superset of the SSCI protocol we have been considering in class. A lot has been written about it, but it is still difficult to comprehend. Using SSCI as a starting point, explain why additional states are necessary, and give (or cite) examples that demonstrate how they work. Ideally, this would still be an overview of the working of the protocol, referencing more detailed documentation on the Web.

=== A Brief Overview of the SSCI Protocol ===

The Simple Scalable Coherence Interface (SSCI) protocol is a simplified version of the SCI protocol. While the SCI protocol has 29 stable states and many pending states, the SSCI protocol has only 3 states. Consequently, many race conditions are possible. Here we give a brief overview of the SSCI protocol, and elaborate on the possible race conditions in the final section.

As previously states, in the SSCI protocol the memory directory is in one of three states. They are:
 
<ul>
<li>UNOWNED - the block is unowned by any cache.</li>
<li>SHARED - the block is owned by multiple caches. Main memory is up to date.</li>
<li>EXCLUSIVE/MODIFIED - the (possibly dirty) block is owned by a single cache. Main memory is possibly out of date.</li>
</ul>

=== A Brief Overview of the SCI Protocol ===

==== Memory Directory States ====
Similar to the SSCI protocol, in SCI the memory directory is one of three states:
 
<ul>
<li>HOME - no remote cache contains a copy of the block.</li>
<li>FRESH - one of more remote caches may have a read-only copy of the block. Main memory is up to date.</li>
<li>GONE - the cache at the head of the sharing list contains an exclusive (possibly dirty) copy of the block.</li>
</ul>

==== Cache States ====
Additionally, each cache has a state, either stable or pending. Stable states have two parts: 
<ol>
<li>Where the cache entry is located in the sharing list for that block</li>
<ul>
<li>ONLY - singleton list</li>
<li>HEAD - head of sharing list of more than one node</li>
<li>MID - not head or tail of sharing list of more than one node</li>
<li>TAIL - tail of sharing list of more than one node</li>
</ul>
<li>State of the cached block</li>
<ul>
<li>DIRTY - modified and writable</li>
<li>CLEAN - unmodified and writable, same contents as memory</li>
<li>FRESH - data is readable and writable, but memory must be informed before memory is written</li>
<li>COPY - unmodified and readable</li>
<li>many others</li>
</ul>
</ol>

These two parts together describe the cache state, e.g. FRESH-ONLY or MID-VALID.

==== List Operations ====
SCI defines three primitive list operations for shared lists:
<ol>
<li>List construction - adding a new node to the head of the sharing list</li>
<li>Rollout - removing a node from the sharing list</li>
<li>Invalidation - invalidate all other sharers. Can only be performed by the head node.</li>
</ol>

=== Why Additional States are Needed ===

The principle difference between SCI and SSCI is that SCI provides mechanisms for '''resolving race conditions''' and '''preserving serialization'''.

==== Example 1 ====
Suppose some processor, say P1, issues a read request and misses on some block that is not cached by any processor. So, the block will have to be fetched from main memory (or possibly some remote cache), and the line will be put into P1's local cache. Space will have to be allocated in P1's cache, usually by evicting some other line. 

In the SSCI protocol, P1 will send a READ message to the home directory. The home directory will reply with the data and set its state to EM, and its head pointer to 1. Upon receipt, P1 will put the block in the allocated line, set its state to E (from the MESI protocol), and its next/previous pointers to 0. 

Consider what might happen if two processors both read miss concurrently. Suppose that P1 and P2 simultaneously send read request to the home node, and the home node processes the request from P1 first. Now, after the home node has updated its state to "EM" and its head pointer to 1, but before P1 has received the ReplyD, the home node processes the request from P2. The home node will set its state to S, update its head pointer to 2 and send a ReplyID(H->P2) telling P2 that P1 has the data. 

Due to network latency, it's possible that P2 will receive the ReplyID and send a WB+Int+UpdPtr(P2->P1), and that P1 will receive that message before it even received the data from the home node! So, because P1's read is not atomic, we have a race condition. 

Now let's consider the same scenario in SCI. 

P1 and P2 both read miss. Both set aside space for the line to be read in, set the state of that line to a "pending" state, and issue the read request to the home node. When the home node receives the request from P1, the memory directory will be in state HOME (since the block is not cached anywhere). It will set its state to FRESH, set its head pointer to 1, and reply with the data. 

Now P2's request is processed by the home node. Since the home node is in state FRESH, its data is up to date. It sets its head pointer to 2 and replies to P2 with the data, and the "old" head pointer (P1). 

P2 receives the data, but the action is not complete until it receives "permission" from P1 to become the new head of the list. So, P2 remains in a pending state and sends a request to P1 to become the new head of the list. Recall that in our scenario, due to network latency, P1 still hasn't received the initial response from the home directory; P1 is still in a pending state. Under the SCI protocol, if a processor is in a pending state when it receives a list operation request (such as becoming the new head of the list), it will extend the pending list backwards. That is, P2 will be put at the head of the list, but in a "pending" state. When P1 completes its operation and becomes the "true" head of the list, it can then pass the "true head" status on to P2. In this way, read requests are atomic and we avoid the race condition sufferred under the SSCI protocol (albeit by adding more complexity). 

==== Example 2 ====

Suppose some block of data is being shared among several caches. Our linked list of sharers is P1-P2-P3-P4-P5. P3 needs to purge the line containing that block of data. 

Under the SSCI protocol, P3 will send an UpdPtr message to the processors represented by the previous and next pointers (P2 and P4 respectively). P2 will set its next pointer to P4, and P4 will set its next pointer to P2. 

Consider what might happen if P3 and P4 concurrently purge the lines of shared data.
<ul>
<li>P3 send UpdPtr(P3->P2) and UpdPtr(P3->P4) and purges its data</li>
<li>Concurrently, P4 sends UpdPtr(P4->P3) and UpdPtr(P4->P5) and purges its data</li>
<li>P2 received the UpdPtr from P3 and sets its "next" pointer to P4</li>
</ul>
Since P4 has already purged and is no longer in the list of sharers, we have a race condition. 
Now let's examine the same scenario under the SCI protocol. 
<ul>
<li>P3 and P4 both put themselves in a pending state.</li>

</ul>

=== Links ===

http://www.scizzl.com/WhatIsSCI.html 
http://www.lrr.in.tum.de/~gerndt/home/Teaching/scalable_shared_memory_systems/Kapitel8.pdf

CSC/ECE 506 Fall 2007/wiki3 2 aY3w

2007-10-17T15:29:39Z

Jfswaffo:

CSC/ECE 506 Fall 2007/wiki3 2 aY3w

2007-10-17T14:14:51Z

Jfswaffo: /* A Brief Overview of the SCI Protocol */

CSC/ECE 506 Fall 2007/wiki3 2 aY3w

2007-10-17T14:00:26Z

Jfswaffo: /* Cache States */

CSC/ECE 506 Fall 2007/wiki3 2 aY3w

2007-10-17T13:48:54Z

Jfswaffo:

CSC/ECE 506 Fall 2007/wiki1 2 3K8i

2007-09-10T20:45:20Z

Jfswaffo:

''Section 1.1.1, first half: Scientific/engineering application trends. What characterizes present-day applications? How much memory, processor time, etc.? How high is the speedup?''

== Trends in Scientific and Engineering Computing ==
Scientific and engineering applications continue to demand the highest performance computers available, a trend established in the early days of supercomputers that continues today in the realm of "High Performance Computing" (HPC). Interestingly, an increasing number of applications are being designed to run on more modest platforms, such as a cluster of commodity processors.

Much work has been done in the areas of computational modeling and simulation. By using modeling, scientists are able to analyze hypothetical designs, rather than relying on empirical evidence, which is often difficult or impossible to come by. Higher performance computers afford the resources to build richer, more complicated models that allow scientists to study more difficult problems. As problems are solved, new, more complex problems arise to take their place. Many Grand Challenge Problems "on the radar" today were not feasible on the supercomputers of a just decade ago. Generally, each successive generation of Grand Challenge problems ''require more memory and faster processing capabilities''. The architectures used to deliver those memory and processing speed requirements are changing, and along with them the algorithms and techniques used to make efficient use of them.

Before looking at some of today's most challenging computational problems, it may be instructive to look at the trends in HPC over the last decade or so.

== Hardware Trends ==

=== Architecture Evolution ===
According the the U.S. Army Research Laboratory, there have been five generations of architectures in the realm of scientific computing . They are serial processors (1947-1986), vector processors (1986-2002), shared memory (1993-present), distributed memory (2000-present), and commodity clusters (2001-present) [http://www.arl.army.mil/www/default.cfm?Action=20&Page=272].

Indeed, the trend in recent years in multiprocessing has been away from vector architectures and towards low cost, multi-threaded single address spaced systems [http://www.nus.edu.sg/comcen/svu/publications/SVULink/vol_1_iss_1/hpc-trends.html]. Multi-core processors are becoming more and more mainstream. Today, many new desktop systems contain dual cores, with some quad cores being sold. [http://en.wikipedia.org/wiki/Tony_Hey Tony Hey], a leading researcher in parallel computing, has predicted that by 2015, a single socket will contain hundreds of cores [http://www.accessmylibrary.com/coms2/summary_0286-30177016_ITM].

=== Cluster and Grid Computing ===
There have also been strong trends towards [http://en.wikipedia.org/wiki/Cluster_computing cluster] and [http://en.wikipedia.org/wiki/Grid_computing grid] computing, which seek to take advantage of multiple, low cost (commodity) computer systems and treat them as a logical entity. Several categories of clusters exists, ranging from high performance computers linked together via high speed interconnects, to geographically separated systems linked together over the Internet [http://en.wikipedia.org/wiki/Cluster_computing]. Grid computing is a form of the latter, generally composed of multiple "collections" of computers (grid elements) that do not necessarily trust each other.

=== Why it is This Way ===
Putting these together, we see a clear movement towards commodity processors in both the areas of parallel computing (processors in a single computer system) and distributed computing (using multiple computer systems). Perhaps the strongest driving force behind these trends is one of supply and demand, or economies of scale. Specialized hardware is, by definition, in less demand then general purpose hardware, making it much more difficult to recover design and production costs. Hence, there is a strong economic incentive for consumers and manufacturers alike to favor more general purpose solutions.

=== Supercomputers: faster than ever ===
Despite these trends, the "traditional" supercomputer is alive and well. Today's highest performance machines are capable of performing hundreds of teraflops per second. (A teraflop is 1 x 10^12 FLOPS.) As of June 2007, the world's fastest computer, as measured by the [http://en.wikipedia.org/wiki/Linpack Linpack Benchmark], is IBM's massively parallel Blue Gene/L. IBM has plans to build a 3 petaflop (3 x 10^15 FLOPS) machine by fall 2007, and a 10 petaflop machine in the 2010-2012 timeframe. More information on IBM's Blue Gene and other supercomputers can be found at [http://www.top500.org Top500.org].

== Software Trends ==
With dramatic increases in hardware performance come more demanding applications, which in turn demand higher performance software. Many scientific applications available today, some even commercially, were not available on general purpose architectures even a few years ago.

=== Multiprocessor Capabilities ===
An increasing number of scientific/engineering applications, such as Mathematica 6 by Wolfram Research, are becoming '''multiprocessor capable'''.
While Mathematica does not ''require'' multiple processors, it does benefit from them, particularly when performing long running linear algebra equations or when dealing with machine-precision real numbers. Mathematica requires a significant amount of RAM (at least, from the average personal computer) - at least 512mb. Wolfram does offer a [http://www.wolfram.com/products/applications/parallel parallel computing toolkit] that allows Mathematica application designers to take advantage of various parallel architectures, ranging from shared memory multiprocessor machines to supercomputers. Wolfram also offers a version of Mathematica tailored to cluster/grid computing, see [http://www.wolfram.com/products/gridmathematica/ http://www.wolfram.com/products/gridmathematica/].

=== Virtualization ===
There is a trend in HPC towards [http://en.wikipedia.org/wiki/Virtualization '''virtualization''']. Virtualization allows application programmers to write applications for virtual machines, not concerning themselves with physical platforms. There are many benefits to running on virtual machines, among them the ability to seamlessly migrate the virtual machines (along with its running applications) off its physical host machine. However, in practice there are many challenges related to virtualization, chief among them the performance limitations they impose [http://www.scientificcomputing.com/ShowPR~PUBCODE~030~ACCT~3000000100~ISSUE~0707~RELTYPE~HPCC~PRODCODE~00000000~PRODLETT~C.html].

=== Visualization ===
Another trend that continues today is the [http://en.wikipedia.org/wiki/Scientific_visualization '''visualization'''] of structured, complex data. Visualization often make complex concepts easier to understand. [http://en.wikipedia.org/wiki/Medical_imaging Medical imaging] allows doctors to visualize internal organs without surgery. There are an almost endless number of domains which use data visualization, such as [http://en.wikipedia.org/wiki/Molecular_geometry molecular geometry], [http://en.wikipedia.org/wiki/Weather_forecasting weather forecasting], [http://en.wikipedia.org/wiki/Fluid_dynamics fluid dynamics], and [http://en.wikipedia.org/wiki/Earth_sciences earth sciences].

Visualization is a memory intensive process. How much so depends on the data set being rendered, but most modern PCs are now capable of running applications with complex visualization capabilities. Several products, such as those from [http://www.avs.com/index_nf.html Advanced Visual Systems], offer software development kits to aid developers in incorporating visualization into their applications.

=== Hardware Requirements/Utilization ===
Generalizing from these examples, modern day scientific/engineering applications are becoming increasingly more capable and more demanding of system resources (RAM and CPU). However, many are targeted for consumer hardware platforms. Many applications are now multiprocessor capable. In the best case, the speedup obtained from having multiple processors is near linear, but normally the speedup is somewhat less, depending on how well the problem parallelizes, how well the program is written, and the communication latency.

== Applications for HPC ==
Some problems are so complex that to solve them would require a significant increase (in some cases by orders of magnitude) in the current computational capabilities of today's computers. These problems are loosely defined as "Grand Challenge Problems." Grand Challenge problems are problems that are solvable, but not in a reasonable period of time on today's computers. Further, a Grand Challenge problem is a problem of some importance, either socially or economically.

Below are a sample of scientific/engineering applications that employ HPC. (Note: not all are classified as "Grand Challenge" problems, but all are challenging!)

=== Biology ===
[http://en.wikipedia.org/wiki/Human_genome_project Human Genome Project (HGP)].
The goal of the HGP is to "understand the genetic makeup of the human species." By some definitions of "complete sequencing" this work was completed in 2003. However, some work remains in that large area of the genome remain unsequenced. Some estimate the genome to be 92% sequenced. The remaining portions , highly repetitive sequences of DNA known as centromeres, are proving difficult with today's technology.

The basic approach to HGP is a classic "divide and conquer". The genome was broken down into smaller pieces, approximately 150,000 base pairs in length, processed separately, then assembled to form chromosones.

=== Physics ===
Distributed and parallel computing is playing an increasing role in physics, including Particle Beam Physics. [http://www.sciencedirect.com/science?_ob=ArticleURL&_udi=B6TJM-4B5R97X-3&_user=10&_coverDate=02%2F21%2F2004&_rdoc=1&_fmt=&_orig=search&_sort=d&view=c&_acct=C000050221&_version=1&_urlVersion=0&_userid=10&md5=721502408864d5addf95e432dfe4e0fe This paper]
examines computational techniques in which cluster computing can be employed for a variety of beam physics problems.

The University of California at Santa Cruz uses a supercomputer to model supernova explosions, galaxy formation, and the fluid dynamics of the interiors of stars and planets. [http://www.unisci.com/stories/20021/0204026.htm]

=== Space Exploration ===
[http://www.seti.org Search for Extraterrestrial Intelligence (SETI)]. SETI's stated mission is to "explore, understand and explain the origin, nature and prevalence of life in the universe." The SETI@Home project (which is not an official project of SETI) uses CPU cycles from millions of computers to process data from the Arecibo Radio Telescope, in Puerto Rico. To take part in the project, users simply download and install a screensaver which, when activated, downloads and processes data, then uploads the results.

=== Weather Forecasting ===
Weather forecasting, a classic "supercomputer" problem, remains in the realm of supercomputers and will for the foreseeable future. Weather forecasting technology continues to improve, not only from increased hardware performance but also by improved software/modeling capabilities. Three day forecasts today are as accurate as one day forecast just 20 years ago [http://www.hpcwire.com/hpcwire/hpcwireWWW/04/0813/108178.html].

=== Game Playing===
Checkers was solved by the program [http://www.cs.ualberta.ca/~chinook/project/ Chinook] in March 2007, after over a decade of a dozen or more computers working nonstop on the problem. The search space for checkers is rather large - 5x10^20 nodes. (Chess is estimated at 10^44, which probably exceeds the number of molecules in the universe.) A number of [http://www.cs.ualberta.ca/~chinook/publications/research.html research publications] have emerged from the Chinook project, including "APHID - Asynchronous Parallel Game Tree Search", and "Distributed Game-Tree Searching Using Transposition Table Driven Work Schedule."

CSC/ECE 506 Fall 2007/wiki1 2 3K8i

2007-09-10T20:40:20Z

Jfswaffo:

''Section 1.1.1, first half: Scientific/engineering application trends. What characterizes present-day applications? How much memory, processor time, etc.? How high is the speedup?''

== Trends in Scientific and Engineering Computing ==
Scientific and engineering applications continue to demand the highest performance computers available, a trend established in the early days of supercomputers that continues today in the realm of "High Performance Computing" (HPC). Interestingly, an increasing number of applications are being designed to run on more modest platforms, such as a cluster of commodity processors.

Much work has been done in the areas of computational modeling and simulation. By using modeling, scientists are able to analyze hypothetical designs, rather than relying on empirical evidence, which is often difficult or impossible to come by. Higher performance computers afford the resources to build richer, more complicated models that allow scientists to study more difficult problems. As problems are solved, new, more complex problems arise to take their place. Many Grand Challenge Problems "on the radar" today were not feasible on the supercomputers of a just decade ago. Generally, each successive generation of Grand Challenge problems ''require more memory and faster processing capabilities''. The architectures used to deliver those memory and processing speed requirements are changing, and along with them the algorithms and techniques used to make efficient use of them.

Before looking at some of today's most challenging computational problems, it may be instructive to look at the trends in HPC over the last decade or so.

== Hardware Trends ==
According the the U.S. Army Research Laboratory, there have been five generations of architectures in the realm of scientific computing . They are serial processors (1947-1986), vector processors (1986-2002), shared memory (1993-present), distributed memory (2000-present), and commodity clusters (2001-present) [http://www.arl.army.mil/www/default.cfm?Action=20&Page=272].

Indeed, the trend in recent years in multiprocessing has been away from vector architectures and towards low cost, multi-threaded single address spaced systems [http://www.nus.edu.sg/comcen/svu/publications/SVULink/vol_1_iss_1/hpc-trends.html]. Multi-core processors are becoming more and more mainstream. Today, many new desktop systems contain dual cores, with some quad cores being sold. [http://en.wikipedia.org/wiki/Tony_Hey Tony Hey], a leading researcher in parallel computing, has predicted that by 2015, a single socket will contain hundreds of cores [http://www.accessmylibrary.com/coms2/summary_0286-30177016_ITM].

There have also been strong trends towards [http://en.wikipedia.org/wiki/Cluster_computing cluster] and [http://en.wikipedia.org/wiki/Grid_computing grid] computing, which seek to take advantage of multiple, low cost (commodity) computer systems and treat them as a logical entity. Several categories of clusters exists, ranging from high performance computers linked together via high speed interconnects, to geographically separated systems linked together over the Internet [http://en.wikipedia.org/wiki/Cluster_computing]. Grid computing is a form of the latter, generally composed of multiple "collections" of computers (grid elements) that do not necessarily trust each other.

Putting these together, we see a clear movement towards commodity processors in both the areas of parallel computing (processors in a single computer system) and distributed computing (using multiple computer systems). Perhaps the strongest driving force behind these trends is one of supply and demand, or economies of scale. Specialized hardware is, by definition, in less demand then general purpose hardware, making it much more difficult to recover design and production costs. Hence, there is a strong economic incentive for consumers and manufacturers alike to favor more general purpose solutions.

Despite these trends, the "traditional" supercomputer is alive and well. Today's highest performance machines are capable of performing hundreds of teraflops per second. (A teraflop is 1 x 10^12 FLOPS.) As of June 2007, the world's fastest computer, as measured by the [http://en.wikipedia.org/wiki/Linpack Linpack Benchmark], is IBM's massively parallel Blue Gene/L. IBM has plans to build a 3 petaflop (3 x 10^15 FLOPS) machine by fall 2007, and a 10 petaflop machine in the 2010-2012 timeframe. More information on IBM's Blue Gene and other supercomputers can be found at [http://www.top500.org Top500.org].

== Software Trends ==
With dramatic increases in hardware performance come more demanding applications, which in turn demand higher performance software. Many scientific applications available today, some even commercially, were not available on general purpose architectures even a few years ago.

=== Multiprocessor Capabilities ===
An increasing number of scientific/engineering applications, such as Mathematica 6 by Wolfram Research, are becoming '''multiprocessor capable'''.
While Mathematica does not ''require'' multiple processors, it does benefit from them, particularly when performing long running linear algebra equations or when dealing with machine-precision real numbers. Mathematica requires a significant amount of RAM (at least, from the average personal computer) - at least 512mb. Wolfram does offer a [http://www.wolfram.com/products/applications/parallel parallel computing toolkit] that allows Mathematica application designers to take advantage of various parallel architectures, ranging from shared memory multiprocessor machines to supercomputers. Wolfram also offers a version of Mathematica tailored to cluster/grid computing, see [http://www.wolfram.com/products/gridmathematica/ http://www.wolfram.com/products/gridmathematica/].

=== Virtualization ===
There is a trend in HPC towards [http://en.wikipedia.org/wiki/Virtualization '''virtualization''']. Virtualization allows application programmers to write applications for virtual machines, not concerning themselves with physical platforms. There are many benefits to running on virtual machines, among them the ability to seamlessly migrate the virtual machines (along with its running applications) off its physical host machine. However, in practice there are many challenges related to virtualization, chief among them the performance limitations they impose [http://www.scientificcomputing.com/ShowPR~PUBCODE~030~ACCT~3000000100~ISSUE~0707~RELTYPE~HPCC~PRODCODE~00000000~PRODLETT~C.html].

=== Visualization ===
Another trend that continues today is the [http://en.wikipedia.org/wiki/Scientific_visualization '''visualization'''] of structured, complex data. Visualization often make complex concepts easier to understand. [http://en.wikipedia.org/wiki/Medical_imaging Medical imaging] allows doctors to visualize internal organs without surgery. There are an almost endless number of domains which use data visualization, such as [http://en.wikipedia.org/wiki/Molecular_geometry molecular geometry], [http://en.wikipedia.org/wiki/Weather_forecasting weather forecasting], [http://en.wikipedia.org/wiki/Fluid_dynamics fluid dynamics], and [http://en.wikipedia.org/wiki/Earth_sciences earth sciences].

Visualization is a memory intensive process. How much so depends on the data set being rendered, but most modern PCs are now capable of running applications with complex visualization capabilities. Several products, such as those from [http://www.avs.com/index_nf.html Advanced Visual Systems], offer software development kits to aid developers in incorporating visualization into their applications.

=== Hardware Requirements/Utilization ===
Generalizing from these examples, modern day scientific/engineering applications are becoming increasingly more capable and more demanding of system resources (RAM and CPU). However, many are targeted for consumer hardware platforms. Many applications are now multiprocessor capable. In the best case, the speedup obtained from having multiple processors is near linear, but normally the speedup is somewhat less, depending on how well the problem parallelizes, how well the program is written, and the communication latency.

== Applications for HPC ==
Some problems are so complex that to solve them would require a significant increase (in some cases by orders of magnitude) in the current computational capabilities of today's computers. These problems are loosely defined as "Grand Challenge Problems." Grand Challenge problems are problems that are solvable, but not in a reasonable period of time on today's computers. Further, a Grand Challenge problem is a problem of some importance, either socially or economically.

Below are a sample of scientific/engineering applications that employ HPC. (Note: not all are classified as "Grand Challenge" problems, but all are challenging!)

=== Biology ===
[http://en.wikipedia.org/wiki/Human_genome_project Human Genome Project (HGP)].
The goal of the HGP is to "understand the genetic makeup of the human species." By some definitions of "complete sequencing" this work was completed in 2003. However, some work remains in that large area of the genome remain unsequenced. Some estimate the genome to be 92% sequenced. The remaining portions , highly repetitive sequences of DNA known as centromeres, are proving difficult with today's technology.

The basic approach to HGP is a classic "divide and conquer". The genome was broken down into smaller pieces, approximately 150,000 base pairs in length, processed separately, then assembled to form chromosones.

=== Physics ===
Distributed and parallel computing is playing an increasing role in physics, including Particle Beam Physics. [http://www.sciencedirect.com/science?_ob=ArticleURL&_udi=B6TJM-4B5R97X-3&_user=10&_coverDate=02%2F21%2F2004&_rdoc=1&_fmt=&_orig=search&_sort=d&view=c&_acct=C000050221&_version=1&_urlVersion=0&_userid=10&md5=721502408864d5addf95e432dfe4e0fe This paper]
examines computational techniques in which cluster computing can be employed for a variety of beam physics problems.

The University of California at Santa Cruz uses a supercomputer to model supernova explosions, galaxy formation, and the fluid dynamics of the interiors of stars and planets. [http://www.unisci.com/stories/20021/0204026.htm]

=== Space Exploration ===
[http://www.seti.org Search for Extraterrestrial Intelligence (SETI)]. SETI's stated mission is to "explore, understand and explain the origin, nature and prevalence of life in the universe." The SETI@Home project (which is not an official project of SETI) uses CPU cycles from millions of computers to process data from the Arecibo Radio Telescope, in Puerto Rico. To take part in the project, users simply download and install a screensaver which, when activated, downloads and processes data, then uploads the results.

=== Weather Forecasting ===
Weather forecasting, a classic "supercomputer" problem, remains in the realm of supercomputers and will for the foreseeable future. Weather forecasting technology continues to improve, not only from increased hardware performance but also by improved software/modeling capabilities. Three day forecasts today are as accurate as one day forecast just 20 years ago [http://www.hpcwire.com/hpcwire/hpcwireWWW/04/0813/108178.html].

=== Game Playing===
Checkers was solved by the program [http://www.cs.ualberta.ca/~chinook/project/ Chinook] in March 2007, after over a decade of a dozen or more computers working nonstop on the problem. The search space for checkers is rather large - 5x10^20 nodes. (Chess is estimated at 10^44, which probably exceeds the number of molecules in the universe.) A number of [http://www.cs.ualberta.ca/~chinook/publications/research.html research publications] have emerged from the Chinook project, including "APHID - Asynchronous Parallel Game Tree Search", and "Distributed Game-Tree Searching Using Transposition Table Driven Work Schedule."

CSC/ECE 506 Fall 2007/wiki1 2 3K8i

2007-09-10T20:37:22Z

Jfswaffo:

''Section 1.1.1, first half: Scientific/engineering application trends. What characterizes present-day applications? How much memory, processor time, etc.? How high is the speedup?''

== Trends in Scientific and Engineering Computing ==
Scientific and engineering applications continue to demand the highest performance computers available, a trend established in the early days of supercomputers that continues today in the realm of "High Performance Computing" (HPC). Interestingly, an increasing number of applications are being designed to run on more modest platforms, such as a cluster of commodity processors.

Much work has been done in the areas of computational modeling and simulation. By using modeling, scientists are able to analyze hypothetical designs, rather than relying on empirical evidence, which is often difficult or impossible to come by. Higher performance computers afford the resources to build richer, more complicated models that allow scientists to study more difficult problems. As problems are solved, new, more complex problems arise to take their place. Many Grand Challenge Problems "on the radar" today were not feasible on the supercomputers of a just decade ago. Generally, each successive generation of Grand Challenge problems require more memory and faster processing capabilities. The architectures used to deliver those memory and processing speed requirements are changing, and along with them the algorithms and techniques used to make efficient use of them.

Before looking at some of today's most challenging computational problems, it may be instructive to look at the trends in HPC over the last decade or so.

== Hardware Trends ==
According the the U.S. Army Research Laboratory, there have been five generations of architectures in the realm of scientific computing . They are serial processors (1947-1986), vector processors (1986-2002), shared memory (1993-present), distributed memory (2000-present), and commodity clusters (2001-present) [http://www.arl.army.mil/www/default.cfm?Action=20&Page=272].

Indeed, the trend in recent years in multiprocessing has been away from vector architectures and towards low cost, multi-threaded single address spaced systems [http://www.nus.edu.sg/comcen/svu/publications/SVULink/vol_1_iss_1/hpc-trends.html]. Multi-core processors are becoming more and more mainstream. Today, many new desktop systems contain dual cores, with some quad cores being sold. [http://en.wikipedia.org/wiki/Tony_Hey Tony Hey], a leading researcher in parallel computing, has predicted that by 2015, a single socket will contain hundreds of cores [http://www.accessmylibrary.com/coms2/summary_0286-30177016_ITM].

There have also been strong trends towards [http://en.wikipedia.org/wiki/Cluster_computing cluster] and [http://en.wikipedia.org/wiki/Grid_computing grid] computing, which seek to take advantage of multiple, low cost (commodity) computer systems and treat them as a logical entity. Several categories of clusters exists, ranging from high performance computers linked together via high speed interconnects, to geographically separated systems linked together over the Internet [http://en.wikipedia.org/wiki/Cluster_computing]. Grid computing is a form of the latter, generally composed of multiple "collections" of computers (grid elements) that do not necessarily trust each other.

Putting these together, we see a clear movement towards commodity processors in both the areas of parallel computing (processors in a single computer system) and distributed computing (using multiple computer systems). Perhaps the strongest driving force behind these trends is one of supply and demand, or economies of scale. Specialized hardware is, by definition, in less demand then general purpose hardware, making it much more difficult to recover design and production costs. Hence, there is a strong economic incentive for consumers and manufacturers alike to favor more general purpose solutions.

Despite these trends, the "traditional" supercomputer is alive and well. Today's highest performance machines are capable of performing hundreds of teraflops per second. (A teraflop is 1 x 10^12 FLOPS.) As of June 2007, the world's fastest computer, as measured by the [http://en.wikipedia.org/wiki/Linpack Linpack Benchmark], is IBM's massively parallel Blue Gene/L. IBM has plans to build a 3 petaflop (3 x 10^15 FLOPS) machine by fall 2007, and a 10 petaflop machine in the 2010-2012 timeframe. More information on IBM's Blue Gene and other supercomputers can be found at [http://www.top500.org Top500.org].

== Software Trends ==
With dramatic increases in hardware performance come more demanding applications, which in turn demand higher performance software. Many scientific applications available today, some even commercially, were not available on general purpose architectures even a few years ago.

=== Multiprocessor Capabilities ===
An increasing number of scientific/engineering applications, such as Mathematica 6 by Wolfram Research, are becoming '''multiprocessor capable'''.
While Mathematica does not ''require'' multiple processors, it does benefit from them, particularly when performing long running linear algebra equations or when dealing with machine-precision real numbers. Mathematica requires a significant amount of RAM (at least, from the average personal computer) - at least 512mb. Wolfram does offer a [http://www.wolfram.com/products/applications/parallel parallel computing toolkit] that allows Mathematica application designers to take advantage of various parallel architectures, ranging from shared memory multiprocessor machines to supercomputers. Wolfram also offers a version of Mathematica tailored to cluster/grid computing, see [http://www.wolfram.com/products/gridmathematica/ http://www.wolfram.com/products/gridmathematica/].

=== Virtualization ===
There is a trend in HPC towards [http://en.wikipedia.org/wiki/Virtualization '''virtualization''']. Virtualization allows application programmers to write applications for virtual machines, not concerning themselves with physical platforms. There are many benefits to running on virtual machines, among them the ability to seamlessly migrate the virtual machines (along with its running applications) off its physical host machine. However, in practice there are many challenges related to virtualization, chief among them the performance limitations they impose [http://www.scientificcomputing.com/ShowPR~PUBCODE~030~ACCT~3000000100~ISSUE~0707~RELTYPE~HPCC~PRODCODE~00000000~PRODLETT~C.html].

=== Visualization ===
Another trend that continues today is the [http://en.wikipedia.org/wiki/Scientific_visualization '''visualization'''] of structured, complex data. Visualization often make complex concepts easier to understand. [http://en.wikipedia.org/wiki/Medical_imaging Medical imaging] allows doctors to visualize internal organs without surgery. There are an almost endless number of domains which use data visualization, such as [http://en.wikipedia.org/wiki/Molecular_geometry molecular geometry], [http://en.wikipedia.org/wiki/Weather_forecasting weather forecasting], [http://en.wikipedia.org/wiki/Fluid_dynamics fluid dynamics], and [http://en.wikipedia.org/wiki/Earth_sciences earth sciences].

Visualization is a memory intensive process. How much so depends on the data set being rendered, but most modern PCs are now capable of running applications with complex visualization capabilities. Several products, such as those from [http://www.avs.com/index_nf.html Advanced Visual Systems], offer software development kits to aid developers in incorporating visualization into their applications.

=== Hardware Requirements/Utilization ===
Generalizing from these examples, modern day scientific/engineering applications are becoming increasingly more capable and more demanding of system resources (RAM and CPU). However, many are targeted for consumer hardware platforms. Many applications are now multiprocessor capable. In the best case, the speedup obtained from having multiple processors is near linear, but normally the speedup is somewhat less, depending on how well the problem parallelizes, how well the program is written, and the communication latency.

== Applications for HPC ==
Some problems are so complex that to solve them would require a significant increase (in some cases by orders of magnitude) in the current computational capabilities of today's computers. These problems are loosely defined as "Grand Challenge Problems." Grand Challenge problems are problems that are solvable, but not in a reasonable period of time on today's computers. Further, a Grand Challenge problem is a problem of some importance, either socially or economically.

Below are a sample of scientific/engineering applications that employ HPC. (Note: not all are classified as "Grand Challenge" problems, but all are challenging!)

=== Biology ===
[http://en.wikipedia.org/wiki/Human_genome_project Human Genome Project (HGP)].
The goal of the HGP is to "understand the genetic makeup of the human species." By some definitions of "complete sequencing" this work was completed in 2003. However, some work remains in that large area of the genome remain unsequenced. Some estimate the genome to be 92% sequenced. The remaining portions , highly repetitive sequences of DNA known as centromeres, are proving difficult with today's technology.

The basic approach to HGP is a classic "divide and conquer". The genome was broken down into smaller pieces, approximately 150,000 base pairs in length, processed separately, then assembled to form chromosones.

=== Physics ===
Distributed and parallel computing is playing an increasing role in physics, including Particle Beam Physics. [http://www.sciencedirect.com/science?_ob=ArticleURL&_udi=B6TJM-4B5R97X-3&_user=10&_coverDate=02%2F21%2F2004&_rdoc=1&_fmt=&_orig=search&_sort=d&view=c&_acct=C000050221&_version=1&_urlVersion=0&_userid=10&md5=721502408864d5addf95e432dfe4e0fe This paper]
examines computational techniques in which cluster computing can be employed for a variety of beam physics problems.

The University of California at Santa Cruz uses a supercomputer to model supernova explosions, galaxy formation, and the fluid dynamics of the interiors of stars and planets. [http://www.unisci.com/stories/20021/0204026.htm]

=== Space Exploration ===
[http://www.seti.org Search for Extraterrestrial Intelligence (SETI)]. SETI's stated mission is to "explore, understand and explain the origin, nature and prevalence of life in the universe." The SETI@Home project (which is not an official project of SETI) uses CPU cycles from millions of computers to process data from the Arecibo Radio Telescope, in Puerto Rico. To take part in the project, users simply download and install a screensaver which, when activated, downloads and processes data, then uploads the results.

=== Weather Forecasting ===
Weather forecasting, a classic "supercomputer" problem, remains in the realm of supercomputers and will for the foreseeable future. Weather forecasting technology continues to improve, not only from increased hardware performance but also by improved software/modeling capabilities. Three day forecasts today are as accurate as one day forecast just 20 years ago [http://www.hpcwire.com/hpcwire/hpcwireWWW/04/0813/108178.html].

=== Game Playing===
Checkers was solved by the program [http://www.cs.ualberta.ca/~chinook/project/ Chinook] in March 2007, after over a decade of a dozen or more computers working nonstop on the problem. The search space for checkers is rather large - 5x10^20 nodes. (Chess is estimated at 10^44, which probably exceeds the number of molecules in the universe.) A number of [http://www.cs.ualberta.ca/~chinook/publications/research.html research publications] have emerged from the Chinook project, including "APHID - Asynchronous Parallel Game Tree Search", and "Distributed Game-Tree Searching Using Transposition Table Driven Work Schedule."

CSC/ECE 506 Fall 2007/wiki1 2 3K8i

2007-09-10T20:08:09Z

Jfswaffo:

''Section 1.1.1, first half: Scientific/engineering application trends. What characterizes present-day applications? How much memory, processor time, etc.? How high is the speedup?''

== Trends in Scientific and Engineering Computing ==
Scientific and engineering applications continue to demand the highest performance computers available, a trend established in the early days of supercomputers that continues today in the realm of "High Performance Computing" (HPC). Interestingly, an increasing number of applications are being designed to run on more modest platforms, such as a cluster of commodity processors.

Much work has been done in the areas of computational modeling and simulation. By using modeling, scientists are able to analyze hypothetical designs, rather than relying on empirical evidence, which is often difficult or impossible to come by. Higher performance computers afford the resources to build richer, more complicated models that allow scientists to study more difficult problems. As problems are solved, new, more complex problems arise to take their place. Many Grand Challenge Problems "on the radar" today were not feasible on the supercomputers of a just decade ago. Generally, each successive generation of Grand Challenge problems require more memory and faster processing capabilities. The architectures used to deliver those memory and processing speed requirements are changing, and along with them the algorithms and techniques used to make efficient use of them.

Before looking at some of today's most challenging computational problems, it may be instructive to look at the trends in HPC over the last decade or so.

== Hardware Trends ==
According the the U.S. Army Research Laboratory, there have been five generations of architectures in the realm of scientific computing . They are serial processors (1947-1986), vector processors (1986-2002), shared memory (1993-present), distributed memory (2000-present), and commodity clusters (2001-present) [http://www.arl.army.mil/www/default.cfm?Action=20&Page=272].

Indeed, the trend in recent years in multiprocessing has been away from vector architectures and towards low cost, multi-threaded single address spaced systems [http://www.nus.edu.sg/comcen/svu/publications/SVULink/vol_1_iss_1/hpc-trends.html]. Multi-core processors are becoming more and more mainstream. Today, many new desktop systems contain dual cores, with some quad cores being sold. [http://en.wikipedia.org/wiki/Tony_Hey Tony Hey], a leading researcher in parallel computing, has predicted that by 2015, a single socket will contain hundreds of cores [http://www.accessmylibrary.com/coms2/summary_0286-30177016_ITM].

There have also been strong trends towards cluster and grid computing, which seek to take advantage of multiple, low cost (commodity) computer systems and treat them as a logical entity. Several categories of clusters exists, ranging from high performance computers linked together via high speed interconnects, to geographically separated systems linked together over the Internet [http://en.wikipedia.org/wiki/Cluster_computing]. Grid computing is a form of the latter, generally composed of multiple "collections" of computers (grid elements) that do not necessarily trust each other.

Putting these together, we see a clear movement towards commodity processors in both the areas of parallel computing (processors in a single computer system) and distributed computing (using multiple computer systems). Perhaps the strongest driving force behind these trends is one of supply and demand, or economies of scale. Specialized hardware is, by definition, in less demand then general purpose hardware, making it much more difficult to recover design and production costs. Hence, there is a strong economic incentive for consumers and manufacturers alike to favor more general purpose solutions.

Despite these trends, the "traditional" supercomputer is alive and well. Today's highest performance machines are capable of performing hundreds of teraflops per second. (A teraflop is 1 x 10^12 FLOPS.) As of June 2007, the world's fastest computer, as measured by the [http://en.wikipedia.org/wiki/Linpack Linpack Benchmark], is IBM's massively parallel Blue Gene/L. IBM has plans to build a 3 petaflop (3 x 10^15 FLOPS) machine by fall 2007, and a 10 petaflop machine in the 2010-2012 timeframe. More information on IBM's Blue Gene and other supercomputers can be found at [http://www.top500.org Top500.org].

== Software Trends ==
With dramatic increases in hardware performance come more demanding applications, which in turn demand higher performance software. Many scientific applications available today, some even commercially, were not available on general purpose architectures even a few years ago.

An increasing number of scientific/engineering applications, such as Mathematica 6 by Wolfram Research, are becoming '''multiprocessor capable'''.
While Mathematica does not ''require'' multiple processors, it does benefit from them, particularly when performing long running linear algebra equations or when dealing with machine-precision real numbers. Mathematica requires a significant amount of RAM (at least, from the average personal computer) - at least 512mb. Wolfram does offer a [http://www.wolfram.com/products/applications/parallel parallel computing toolkit] that allows Mathematica application designers to take advantage of various parallel architectures, ranging from shared memory multiprocessor machines to supercomputers. Wolfram also offers a version of Mathematica tailored to cluster/grid computing, see [http://www.wolfram.com/products/gridmathematica/ http://www.wolfram.com/products/gridmathematica/].

There is a trend in HPC towards '''virtualization'''. Virtualization allows application programmers to write applications for virtual machines, not concerning themselves with physical platforms. There are many benefits to running on virtual machines, among them the ability to seamlessly migrate the virtual machines (along with its running applications) off its physical host machine. However, in practice there are many challenges related to virtualization, chief among them the performance limitations they impose [http://www.scientificcomputing.com/ShowPR~PUBCODE~030~ACCT~3000000100~ISSUE~0707~RELTYPE~HPCC~PRODCODE~00000000~PRODLETT~C.html].

Another trend that continues today is the [http://en.wikipedia.org/wiki/Scientific_visualization '''visualization'''] of structured, complex data. Visualization often make complex concepts easier to understand. [http://en.wikipedia.org/wiki/Medical_imaging Medical imaging] allows doctors to visualize internal organs without surgery. There are an almost endless number of domains which use data visualization, such as [http://en.wikipedia.org/wiki/Molecular_geometry molecular geometry], [http://en.wikipedia.org/wiki/Weather_forecasting weather forecasting], [http://en.wikipedia.org/wiki/Fluid_dynamics fluid dynamics], and [http://en.wikipedia.org/wiki/Earth_sciences earth sciences].

Visualization is a memory intensive process. How much so depends on the data set being rendered, but most modern PCs are now capable of running applications with complex visualization capabilities. Several products, such as those from [http://www.avs.com/index_nf.html Advanced Visual Systems], offer software development kits to aid developers in incorporating visualization into their applications.

== Challenging Problems ==
Some problems are so complex that to solve them would require a significant increase (in some cases by orders of magnitude) in the current computational capabilities of today's computers. These problems are loosely defined as "Grand Challenge Problems." Grand Challenge problems are problems that are solvable, but not in a reasonable period of time on today's computers. Further, a Grand Challenge problem is a problem of some importance, either socially or economically.

Below are a sample of scientific/engineering applications that employ HPC. (Note: not all are classified as "Grand Challenge" problems, but all are challenging!)

'''Biology''' - [http://en.wikipedia.org/wiki/Human_genome_project Human Genome Project (HGP)].
The goal of the HGP is to "understand the genetic makeup of the human species." By some definitions of "complete sequencing" this work was completed in 2003. However, some work remains in that large area of the genome remain unsequenced. Some estimate the genome to be 92% sequenced. The remaining portions , highly repetitive sequences of DNA known as centromeres, are proving difficult with today's technology.

The basic approach to HGP is a classic "divide and conquer". The genome was broken down into smaller pieces, approximately 150,000 base pairs in length, processed separately, then assembled to form chromosones.

'''Physics''' - Distributed and parallel computing is playing an increasing role in physics, including Particle Beam Physics. [http://www.sciencedirect.com/science?_ob=ArticleURL&_udi=B6TJM-4B5R97X-3&_user=10&_coverDate=02%2F21%2F2004&_rdoc=1&_fmt=&_orig=search&_sort=d&view=c&_acct=C000050221&_version=1&_urlVersion=0&_userid=10&md5=721502408864d5addf95e432dfe4e0fe This paper]
examines computational techniques in which cluster computing can be employed for a variety of beam physics problems.

The University of California at Santa Cruz uses a supercomputer to model supernova explosions, galaxy formation, and the fluid dynamics of the interiors of stars and planets. [http://www.unisci.com/stories/20021/0204026.htm]

'''Space Exploration''' - [http://www.seti.org Search for Extraterrestrial Intelligence (SETI)]. SETI's stated mission is to "explore, understand and explain the origin, nature and prevalence of life in the universe." The SETI@Home project (which is not an official project of SETI) uses CPU cycles from millions of computers to process data from the Arecibo Radio Telescope, in Puerto Rico. To take part in the project, users simply download and install a screensaver which, when activated, downloads and processes data, then uploads the results.

'''Weather Forecasting''' - Weather forecasting, a classic "supercomputer" problem, remains in the realm of supercomputers and will for the foreseeable future. Weather forecasting technology continues to improve, not only from increased hardware performance but also by improved software/modeling capabilities. Three day forecasts today are as accurate as one day forecast just 20 years ago [http://www.hpcwire.com/hpcwire/hpcwireWWW/04/0813/108178.html].

'''Game Playing''' - Checkers was solved by the program [http://www.cs.ualberta.ca/~chinook/project/ Chinook] in March 2007, after over a decade of a dozen or more computers working nonstop on the problem. The search space for checkers is rather large - 5x10^20 nodes. (Chess is estimated at 10^44, which probably exceeds the number of molecules in the universe.) A number of [http://www.cs.ualberta.ca/~chinook/publications/research.html research publications] have emerged from the Chinook project, including "APHID - Asynchronous Parallel Game Tree Search", and "Distributed Game-Tree Searching Using Transposition Table Driven Work Schedule."

CSC/ECE 506 Fall 2007/wiki1 2 3K8i

2007-09-10T19:24:27Z

Jfswaffo:

''Section 1.1.1, first half: Scientific/engineering application trends. What characterizes present-day applications? How much memory, processor time, etc.? How high is the speedup?''

== Trends in Scientific and Engineering Computing ==
Scientific and engineering applications continue to demand the highest performance computers available, a trend established in the early days of supercomputers that continues today in the realm of "High Performance Computing" (HPC). Interestingly, an increasing number of applications are being designed to run on more modest platforms, such as a cluster of commodity processors.

Much work has been done in the areas of computational modeling and simulation. By using modeling, scientists are able to analyze hypothetical designs, rather than relying on empirical evidence, which is often difficult or impossible to come by. Higher performance computers afford the resources to build richer, more complicated models that allow scientists to study more difficult problems. As problems are solved, new, more complex problems arise to take their place. Many Grand Challenge Problems "on the radar" today were not feasible on the supercomputers of a just decade ago. Generally, each successive generation of Grand Challenge problems require more memory and faster processing capabilities. The architectures used to deliver those memory and processing speed requirements are changing, and along with them the algorithms and techniques used to make efficient use of them.

Before looking at some of today's most challenging computational problems, it may be instructive to look at the trends in HPC over the last decade or so.

== Hardware Trends ==
According the the U.S. Army Research Laboratory, there have been five generations of architectures in the realm of scientific computing . They are serial processors (1947-1986), vector processors (1986-2002), shared memory (1993-present), distributed memory (2000-present), and commodity clusters (2001-present) [http://www.arl.army.mil/www/default.cfm?Action=20&Page=272].

Indeed, the trend in recent years in multiprocessing has been away from vector architectures and towards low cost, multi-threaded single address spaced systems [http://www.nus.edu.sg/comcen/svu/publications/SVULink/vol_1_iss_1/hpc-trends.html]. Multi-core processors are becoming more and more mainstream. Today, many new desktop systems contain dual cores, with some quad cores being sold. [http://en.wikipedia.org/wiki/Tony_Hey Tony Hey], a leading researcher in parallel computing, has predicted that by 2015, a single socket will contain hundreds of cores [http://www.accessmylibrary.com/coms2/summary_0286-30177016_ITM].

There have also been strong trends towards cluster and grid computing, which seek to take advantage of multiple, low cost (commodity) computer systems and treat them as a logical entity. Several categories of clusters exists, ranging from high performance computers linked together via high speed interconnects, to geographically separated systems linked together over the Internet [http://en.wikipedia.org/wiki/Cluster_computing]. Grid computing is a form of the latter, generally composed of multiple "collections" of computers (grid elements) that do not necessarily trust each other.

Putting these together, we see a clear movement towards commodity processors in both the areas of parallel computing (processors in a single computer system) and distributed computing (using multiple computer systems). Perhaps the strongest driving force behind these trends is one of supply and demand, or economies of scale. Specialized hardware is, by definition, in less demand then general purpose hardware, making it much more difficult to recover design and production costs. Hence, there is a strong economic incentive for consumers and manufacturers alike to favor more general purpose solutions.

Despite these trends, the "traditional" supercomputer is alive and well. Today's highest performance machines are capable of performing hundreds of teraflops per second. (A teraflop is 1 x 10^12 FLOPS.) As of June 2007, the world's fastest computer, as measured by the [http://en.wikipedia.org/wiki/Linpack Linpack Benchmark], is IBM's massively parallel Blue Gene/L. IBM has plans to build a 3 petaflop (3 x 10^15 FLOPS) machine by fall 2007, and a 10 petaflop machine in the 2010-2012 timeframe. More information on IBM's Blue Gene and other supercomputers can be found at [http://www.top500.org Top500.org].

== Software Trends ==
With dramatic increases in hardware performance come more demanding applications, which in turn demand higher performance software. Many scientific applications available today, some even commercially, were not available on general purpose architectures even a few years ago.

'''Mathematica 6''' by Wolfram Research, is one of a growing number of commercially available scientific/engineering applications. Mathematica does not require multiple processors, but does require significant resources (at least, from the "average" personal computer) - at least 512mb memory. However, on many operating systems Mathematica is able to take advantage of multiple processors, particularly when doing linear algebra equations and dealing with machine-precision real numbers. Wolfram does offer a [http://www.wolfram.com/products/applications/parallel parallel computing toolkit] that allows Mathematica application designers to take advantage of various parallel architectures, ranging from shared memory multiprocessor machines to supercomputers. Wolfram also offers a version of Mathematica tailored to cluster/grid computing, see [http://www.wolfram.com/products/gridmathematica/ http://www.wolfram.com/products/gridmathematica/].

There is a trend in HPC towards '''virtualization'''. Virtualization allows application programmers to write applications for virtual machines, not concerning themselves with physical platforms. There are many benefits to running on virtual machines, among them the ability to seamlessly migrate the virtual machines (along with its running applications) off its physical host machine. However, in practice there are many challenges related to virtualization, chief among them the performance limitations they impose [http://www.scientificcomputing.com/ShowPR~PUBCODE~030~ACCT~3000000100~ISSUE~0707~RELTYPE~HPCC~PRODCODE~00000000~PRODLETT~C.html].

== Challenging Problems ==
Some problems are so complex that to solve them would require a significant increase (in some cases by orders of magnitude) in the current computational capabilities of today's computers. These problems are loosely defined as "Grand Challenge Problems." Grand Challenge problems are problems that are solvable, but not in a reasonable period of time on today's computers. Further, a Grand Challenge problem is a problem of some importance, either socially or economically.

Below are a sample of scientific/engineering applications that employ HPC. (Note: not all are classified as "Grand Challenge" problems, but all are challenging!)

'''Biology''' - [http://en.wikipedia.org/wiki/Human_genome_project Human Genome Project (HGP)].
The goal of the HGP is to "understand the genetic makeup of the human species." By some definitions of "complete sequencing" this work was completed in 2003. However, some work remains in that large area of the genome remain unsequenced. Some estimate the genome to be 92% sequenced. The remaining portions , highly repetitive sequences of DNA known as centromeres, are proving difficult with today's technology.

The basic approach to HGP is a classic "divide and conquer". The genome was broken down into smaller pieces, approximately 150,000 base pairs in length, processed separately, then assembled to form chromosones.

'''Physics''' - Distributed and parallel computing is playing an increasing role in physics, including Particle Beam Physics. [http://www.sciencedirect.com/science?_ob=ArticleURL&_udi=B6TJM-4B5R97X-3&_user=10&_coverDate=02%2F21%2F2004&_rdoc=1&_fmt=&_orig=search&_sort=d&view=c&_acct=C000050221&_version=1&_urlVersion=0&_userid=10&md5=721502408864d5addf95e432dfe4e0fe This paper]
examines computational techniques in which cluster computing can be employed for a variety of beam physics problems.

The University of California at Santa Cruz uses a supercomputer to model supernova explosions, galaxy formation, and the fluid dynamics of the interiors of stars and planets. [http://www.unisci.com/stories/20021/0204026.htm]

'''Space Exploration''' - [http://www.seti.org Search for Extraterrestrial Intelligence (SETI)]. SETI's stated mission is to "explore, understand and explain the origin, nature and prevalence of life in the universe." The SETI@Home project (which is not an official project of SETI) uses CPU cycles from millions of computers to process data from the Arecibo Radio Telescope, in Puerto Rico. To take part in the project, users simply download and install a screensaver which, when activated, downloads and processes data, then uploads the results.

'''Weather Forecasting''' - Weather forecasting, a classic "supercomputer" problem, remains in the realm of supercomputers and will for the foreseeable future. Weather forecasting technology continues to improve, not only from increased hardware performance but also by improved software/modeling capabilities. Three day forecasts today are as accurate as one day forecast just 20 years ago [http://www.hpcwire.com/hpcwire/hpcwireWWW/04/0813/108178.html].

'''Game Playing''' - Checkers was solved by the program [http://www.cs.ualberta.ca/~chinook/project/ Chinook] in March 2007, after over a decade of a dozen or more computers working nonstop on the problem. The search space for checkers is rather large - 5x10^20 nodes. (Chess is estimated at 10^44, which probably exceeds the number of molecules in the universe.) A number of [http://www.cs.ualberta.ca/~chinook/publications/research.html research publications] have emerged from the Chinook project, including "APHID - Asynchronous Parallel Game Tree Search", and "Distributed Game-Tree Searching Using Transposition Table Driven Work Schedule."

CSC/ECE 506 Fall 2007/wiki1 2 3K8i

2007-09-05T15:14:48Z

Jfswaffo:

== Trends in Scientific and Engineering Computing ==

Scientific and engineering applications continue to demand the highest performance computers available, a trend established in the early days of supercomputers that continues today in the realm of "High Performance Computing" (HPC). Interestingly, an increasing number of applications are being designed to run on more modest platforms, such as a cluster of commodity processors.

Much work has been done in the areas of computational modeling and simulation. By using modeling, scientists are able to analyze hypothetical designs, rather than relying on empirical evidence, which is often difficult or impossible to come by. Higher performance computers afford the resources to build richer, more complicated models that allow scientists to study more difficult problems. As problems are solved, new, more complex problems arise to take their place. Many Grand Challenge Problems "on the radar" today were not feasible on the supercomputers of a just decade ago. Generally, each successive generation of Grand Challenge problems require more memory and faster processing capabilities. The architectures used to deliver those memory and processing speed requirements are changing, and along with them the algorithms and techniques used to make efficient use of them.

Before looking at some of today's most challenging computational problems, it may be instructive to look at the trends in HPC over the last decade or so.

== Hardware Trends ==
According the the U.S. Army Research Laboratory (http://www.arl.army.mil/www/default.cfm?Action=20&Page=272), there have been five generations of architectures in the realm of scientific computing. They are serial processors (1947-1986), vector processors (1986-2002), shared memory (1993-present), distributed memory (2000-present), and commodity clusters (2001-present).

Indeed, the trend in recent years in multiprocessing has been away from vector architectures and towards low cost, multi-threaded single address spaced systems. (http://www.nus.edu.sg/comcen/svu/publications/SVULink/vol_1_iss_1/hpc-trends.html) Multi-core processors are becoming more and more mainstream. Today, many new desktop systems contain dual cores, with some quad cores being sold. Tony Hey (http://en.wikipedia.org/wiki/Tony_Hey), a leading researcher in parallel computing, has predicted that by 2015, a single socket will contain hundreds of cores. (http://www.accessmylibrary.com/coms2/summary_0286-30177016_ITM)

There have also been strong trends towards cluster and grid computing, which seek to take advantage of multiple, low cost (commodity) computer systems and treat them as a logical entity. Several categories of clusters exists, ranging from high performance computers linked together via high speed interconnects, to geographically separated systems linked together over the Internet. (http://en.wikipedia.org/wiki/Cluster_computing) Grid computing is a form of the latter, generally composed of multiple "collections" of computers (grid elements) that do not necessarily trust each other.

Putting these together, we see a clear movement towards commodity processors in both the areas of parallel computing (processors in a single computer system) and distributed computing (using multiple computer systems). Perhaps the strongest driving force behind these trends is one of supply and demand, or economies of scale. Specialized hardware is, by definition, in less demand then general purpose hardware, making it much more difficult to recover design and production costs. Hence, there is a strong economic incentive for consumers and manufacturers alike to favor more general purpose solutions.

Despite these trends, the "traditional" supercomputer is alive and well. Today's highest performance machines are capable of performing hundreds of teraflops per second. (A teraflop is 1 x 10^12 FLOPS.) As of June 2007, the world's fastest computer, as measured by the Linpack (http://en.wikipedia.org/wiki/Linpack) benchmark, is IBM's massively parallel Blue Gene/L. IBM has plans to build a 3 petaflop (3 x 10^15 FLOPS) machine by fall 2007, and a 10 petaflop machine in the 2010-2012 timeframe. More information on IBM's Blue Gene and other supercomputers can be found at http://www.top500.org/.

== Software Trends ==
With dramatic increases in hardware performance come more demanding applications, which in turn demand higher performance software. Many scientific applications available today, some even commercially, were not available on general purpose architectures even a few years ago.

'''Mathematica 6''' by Wolfram Research, is one of a growing number of commercially available scientific/engineering applications. Mathematica does not require multiple processors, but does require significant resources (at least, from the "average" personal computer) - at least 512mb memory. However, on many operating systems Mathematica is able to take advantage of multiple processors, particularly when doing linear algebra equations and dealing with machine-precision real numbers. Wolfram does offer a parallel computing toolkit (http://www.wolfram.com/products/applications/parallel) that allows Mathematica application designers to take advantage of various parallel architectures, ranging from shared memory multiprocessor machines to supercomputers. Wolfram also offers a version of Mathematica tailored to cluster/grid computing, see http://www.wolfram.com/products/gridmathematica/.

There is a trend in HPC towards '''virtualization'''. Virtualization allows application programmers to write applications for virtual machines, not concerning themselves with physical platforms. There are many benefits to running on virtual machines, among them the ability to seamlessly migrate the virtual machines (along with its running applications) off its physical host machine. However, in practice there are many challenges related to virtualization, chief among them the performance limitations they impose (http://www.scientificcomputing.com/ShowPR~PUBCODE~030~ACCT~3000000100~ISSUE~0707~RELTYPE~HPCC~PRODCODE~00000000~PRODLETT~C.html).

== Challenging Problems ==
Some problems are so complex that to solve them would require a significant increase (in some cases by orders of magnitude) in the current computational capabilities of today's computers. These problems are loosely defined as "Grand Challenge Problems." Grand Challenge problems are problems that are solvable, but not in a reasonable period of time on today's computers. Further, a Grand Challenge problem is a problem of some importance, either socially or economically.

Below are a sample of scientific/engineering applications that employ HPC. (Note: not all are classified as "Grand Challenge" problems, but all are challenging!)

'''Biology''' - Human Genome Project (HGP) (http://en.wikipedia.org/wiki/Human_genome_project).
The goal of the HGP is to "understand the genetic makeup of the human species." By some definitions of "complete sequencing" this work was completed in 2003. However, some work remains in that large area of the genome remain unsequenced. Some estimate the genome to be 92% sequenced. The remaining portions , highly repetitive sequences of DNA known as centromeres, are proving difficult with today's technology.

The basic approach to HGP is a classic "divide and conquer". The genome was broken down into smaller pieces, approximately 150,000 base pairs in length, processed separately, then assembled to form chromosones.

'''Physics''' - Distributed and parallel computing is playing an increasing role in physics, including Particle Beam Physics. This paper (http://www.sciencedirect.com/science?_ob=ArticleURL&_udi=B6TJM-4B5R97X-3&_user=10&_coverDate=02%2F21%2F2004&_rdoc=1&_fmt=&_orig=search&_sort=d&view=c&_acct=C000050221&_version=1&_urlVersion=0&_userid=10&md5=721502408864d5addf95e432dfe4e0fe)
examines computational techniques in which cluster computing can be employed for a variety of beam physics problems.

The University of California at Santa Cruz uses a supercomputer to model supernova explosions, galaxy formation, and the fluid dynamics of the interiors of stars and planets. (http://www.unisci.com/stories/20021/0204026.htm)

'''Space Exploration''' - Search for Extraterrestrial Intelligence (SETI) (http://www.seti.org/). SETI's stated mission is to "explore, understand and explain the origin, nature and prevalence of life in the universe." The SETI@Home project (which is not an official project of SETI) uses CPU cycles from millions of computers to process data from the Arecibo Radio Telescope, in Puerto Rico. To take part in the project, users simply download and install a screensaver which, when activated, downloads and processes data, then uploads the results.

'''Weather Forecasting''' - Weather forecasting, a classic "supercomputer" problem, remains in the realm of supercomputers and will for the foreseeable future. Weather forecasting technology continues to improve, not only from increased hardware performance but also by improved software/modeling capabilities. Three day forecasts today are as accurate as one day forecast just 20 years ago (http://www.hpcwire.com/hpcwire/hpcwireWWW/04/0813/108178.html).

'''Game Playing''' - Checkers was solved by the program Chinook (http://www.cs.ualberta.ca/~chinook/project/) in March 2007, after over a decade of a dozen or more computers working nonstop on the problem. The search space for checkers is rather large - 5x10^20 nodes. (Chess is estimated at 10^44, which probably exceeds the number of molecules in the universe.) A number of research publications have emerged from the Chinook project (http://www.cs.ualberta.ca/~chinook/publications/research.html), including "APHID - Asynchronous Parallel Game Tree Search", and "Distributed Game-Tree Searching Using Transposition Table Driven Work Schedule."

CSC/ECE 506 Fall 2007/wiki1 2 3K8i

2007-09-05T15:08:51Z

Jfswaffo:

== Trends in Scientific and Engineering Computing ==

Scientific and engineering applications continue to demand the highest performance computers available, a trend established in the early days of supercomputers that continues today in the realm of "High Performance Computing" (HPC). Interestingly, an increasing number of applications are being designed to run on more modest platforms, such as a cluster of commodity processors.

Much work has been done in the areas of computational modeling and simulation. By using modeling, scientists are able to analyze hypothetical designs, rather than relying on empirical evidence, which is often difficult or impossible to come by. Higher performance computers afford the resources to build richer, more complicated models that allow scientists to study more difficult problems. As problems are solved, new, more complex problems arise to take their place. Many Grand Challenge Problems "on the radar" today were not feasible on the supercomputers of a just decade ago. Generally, each successive generation of Grand Challenge problems require more memory and faster processing capabilities. The architectures used to deliver those memory and processing speed requirements are changing, and along with them the algorithms and techniques used to make efficient use of them.

Before looking at some of today's most challenging computational problems, it may be instructive to look at the trends in HPC over the last decade or so.

== Hardware Trends ==
According the the U.S. Army Research Laboratory (http://www.arl.army.mil/www/default.cfm?Action=20&Page=272), there have been five generations of architectures in the realm of scientific computing. They are serial processors (1947-1986), vector processors (1986-2002), shared memory (1993-present), distributed memory (2000-present), and commodity clusters (2001-present).

Indeed, the trend in recent years in multiprocessing has been away from vector architectures and towards low cost, multi-threaded single address spaced systems. (http://www.nus.edu.sg/comcen/svu/publications/SVULink/vol_1_iss_1/hpc-trends.html) Multi-core processors are becoming more and more mainstream. Today, many new desktop systems contain dual cores, with some quad cores being sold. Tony Hey (http://en.wikipedia.org/wiki/Tony_Hey), a leading researcher in parallel computing, has predicted that by 2015, a single socket will contain hundreds of cores. (http://www.accessmylibrary.com/coms2/summary_0286-30177016_ITM)

There have also been strong trends towards cluster and grid computing, which seek to take advantage of multiple, low cost (commodity) computer systems and treat them as a logical entity. Several categories of clusters exists, ranging from high performance computers linked together via high speed interconnects, to geographically separated systems linked together over the Internet. (http://en.wikipedia.org/wiki/Cluster_computing) Grid computing is a form of the latter, generally composed of multiple "collections" of computers (grid elements) that do not necessarily trust each other.

Putting these together, we see a clear movement towards commodity processors in both the areas of parallel computing (processors in a single computer system) and distributed computing (using multiple computer systems). Perhaps the strongest driving force behind these trends is one of supply and demand, or economies of scale. Specialized hardware is, by definition, in less demand then general purpose hardware, making it much more difficult to recover design and production costs. Hence, there is a strong economic incentive for consumers and manufacturers alike to favor more general purpose solutions.

Despite these trends, the "traditional" supercomputer is alive and well. Today's highest performance machines are capable of performing hundreds of teraflops per second. (A teraflop is 1 x 10^12 FLOPS.) As of June 2007, the world's fastest computer, as measured by the Linpack (http://en.wikipedia.org/wiki/Linpack) benchmark, is IBM's massively parallel Blue Gene/L. IBM has plans to build a 3 petaflop (3 x 10^15 FLOPS) machine by fall 2007, and a 10 petaflop machine in the 2010-2012 timeframe. More information on IBM's Blue Gene and other supercomputers can be found at http://www.top500.org/.

== Software Trends ==
With dramatic increases in hardware performance come more demanding applications, which in turn demand higher performance software. Many scientific applications available today, some even commercially, were not available on general purpose architectures even a few years ago.

'''Mathematica 6''' by Wolfram Research, is one of a growing number of commercially available scientific/engineering applications. Mathematica does not require multiple processors, but does require significant resources (at least, from the "average" personal computer) - at least 512mb memory. However, on many operating systems Mathematica is able to take advantage of multiple processors, particularly when doing linear algebra equations and dealing with machine-precision real numbers. Wolfram does offer a parallel computing toolkit (http://www.wolfram.com/products/applications/parallel) that allows Mathematica application designers to take advantage of various parallel architectures, ranging from shared memory multiprocessor machines to supercomputers. Wolfram also offers a version of Mathematica tailored to cluster/grid computing, see http://www.wolfram.com/products/gridmathematica/.

There is a trend in HPC towards '''virtualization'''. Virtualization allows application programmers to write applications for virtual machines, not concerning themselves with physical platforms. There are many benefits to running on virtual machines, among them the ability to seamlessly migrate the virtual machines (along with its running applications) off its physical host machine. However, in practice there are many challenges related to virtualization, chief among them the performance limitations they impose (http://www.scientificcomputing.com/ShowPR~PUBCODE~030~ACCT~3000000100~ISSUE~0707~RELTYPE~HPCC~PRODCODE~00000000~PRODLETT~C.html).

== Challenging Problems ==
Some problems are so complex that to solve them would require a significant increase (in some cases by orders of magnitude) in the current computational capabilities of today's computers. These problems are loosely defined as "Grand Challenge Problems." Grand Challenge problems are problems that are solvable, but not in a reasonable period of time on today's computers. Further, a Grand Challenge problem is a problem of some importance, either socially or economically.

Below are a sample of scientific/engineering applications that employ HPC. (Note: not all are classified as "Grand Challenge" problems, but all are challenging!)

'''Biology''' - Human Genome Project (HGP) (http://en.wikipedia.org/wiki/Human_genome_project).
The goal of the HGP is to "understand the genetic makeup of the human species." By some definitions of "complete sequencing" this work was completed in 2003. However, some work remains in that large area of the genome remain unsequenced. Some estimate the genome to be 92% sequenced. The remaining portions , highly repetitive sequences of DNA known as centromeres, are proving difficult with today's technology.

The basic approach to HGP is a classic "divide and conquer". The genome was broken down into smaller pieces, approximately 150,000 base pairs in length, processed separately, then assembled to form chromosones.

'''Physics''' Distributed and parallel computing is playing an increasing role in physics, including Particle Beam Physics. This paper (http://www.sciencedirect.com/science?_ob=ArticleURL&_udi=B6TJM-4B5R97X-3&_user=10&_coverDate=02%2F21%2F2004&_rdoc=1&_fmt=&_orig=search&_sort=d&view=c&_acct=C000050221&_version=1&_urlVersion=0&_userid=10&md5=721502408864d5addf95e432dfe4e0fe)
examines computational techniques in which cluster computing can be employed for a variety of beam physics problems.

The University of California at Santa Cruz uses a supercomputer to model supernova explosions, galaxy formation, and the fluid dynamics of the interiors of stars and planets. (http://www.unisci.com/stories/20021/0204026.htm)

'''Space Exploration''' - Search for Extraterrestrial Intelligence (SETI) (http://www.seti.org/). SETI's stated mission is to "explore, understand and explain the origin, nature and prevalence of life in the universe." The SETI@Home project (which is not an official project of SETI) uses CPU cycles from millions of computers to process data from the Arecibo Radio Telescope, in Puerto Rico. To take part in the project, users simply download and install a screensaver which, when activated, downloads and processes data, then uploads the results.

'''Weather Forecasting''' - Weather forecasting, a classic "supercomputer" problem, remains in the realm of supercomputers and will for the foreseeable future. Weather forecasting technology continues to improve, not only from increased hardware performance but also by improved software/modeling capabilities. Three day forecasts today are as accurate as one day forecast just 20 years ago (http://www.hpcwire.com/hpcwire/hpcwireWWW/04/0813/108178.html).

'''Game Playing''' - Checkers was solved by the program Chinook (http://www.cs.ualberta.ca/~chinook/project/) in March 2007, after over a decade of a dozen or more computers working nonstop on the problem. The search space for checkers is rather large - 5x10^20 nodes. (Chess is estimated at 10^44, which probably exceeds the number of molecules in the universe.) A number of research publications have emerged from the Chinook project (http://www.cs.ualberta.ca/~chinook/publications/research.html), including "APHID - Asynchronous Parallel Game Tree Search", and "Distributed Game-Tree Searching Using Transposition Table Driven Work Schedule."

CSC/ECE 506 Fall 2007/wiki1 2 3K8i

2007-09-05T15:08:16Z

Jfswaffo:

== Trends in Scientific and Engineering Computing ==

Scientific and engineering applications continue to demand the highest performance computers available, a trend established in the early days of supercomputers that continues today in the realm of "High Performance Computing" (HPC). However, an increasing number of applications are being designed to run on more modest platforms, such as a cluster of commodity processors.

Much work has been done in the areas of computational modeling and simulation. By using modeling, scientists are able to analyze hypothetical designs, rather than relying on empirical evidence, which is often difficult or impossible to come by. Higher performance computers afford the resources to build richer, more complicated models that allow scientists to study more difficult problems. As problems are solved, new, more complex problems arise to take their place. Many Grand Challenge Problems "on the radar" today were not feasible on the supercomputers of a just decade ago. Generally, each successive generation of Grand Challenge problems require more memory and faster processing capabilities. The architectures used to deliver those memory and processing speed requirements are changing, and along with them the algorithms and techniques used to make efficient use of them.

Before looking at some of today's most challenging computational problems, it may be instructive to look at the trends in HPC over the last decade or so.

== Hardware Trends ==
According the the U.S. Army Research Laboratory (http://www.arl.army.mil/www/default.cfm?Action=20&Page=272), there have been five generations of architectures in the realm of scientific computing. They are serial processors (1947-1986), vector processors (1986-2002), shared memory (1993-present), distributed memory (2000-present), and commodity clusters (2001-present).

Indeed, the trend in recent years in multiprocessing has been away from vector architectures and towards low cost, multi-threaded single address spaced systems. (http://www.nus.edu.sg/comcen/svu/publications/SVULink/vol_1_iss_1/hpc-trends.html) Multi-core processors are becoming more and more mainstream. Today, many new desktop systems contain dual cores, with some quad cores being sold. Tony Hey (http://en.wikipedia.org/wiki/Tony_Hey), a leading researcher in parallel computing, has predicted that by 2015, a single socket will contain hundreds of cores. (http://www.accessmylibrary.com/coms2/summary_0286-30177016_ITM)

There have also been strong trends towards cluster and grid computing, which seek to take advantage of multiple, low cost (commodity) computer systems and treat them as a logical entity. Several categories of clusters exists, ranging from high performance computers linked together via high speed interconnects, to geographically separated systems linked together over the Internet. (http://en.wikipedia.org/wiki/Cluster_computing) Grid computing is a form of the latter, generally composed of multiple "collections" of computers (grid elements) that do not necessarily trust each other.

Putting these together, we see a clear movement towards commodity processors in both the areas of parallel computing (processors in a single computer system) and distributed computing (using multiple computer systems). Perhaps the strongest driving force behind these trends is one of supply and demand, or economies of scale. Specialized hardware is, by definition, in less demand then general purpose hardware, making it much more difficult to recover design and production costs. Hence, there is a strong economic incentive for consumers and manufacturers alike to favor more general purpose solutions.

Despite these trends, the "traditional" supercomputer is alive and well. Today's highest performance machines are capable of performing hundreds of teraflops per second. (A teraflop is 1 x 10^12 FLOPS.) As of June 2007, the world's fastest computer, as measured by the Linpack (http://en.wikipedia.org/wiki/Linpack) benchmark, is IBM's massively parallel Blue Gene/L. IBM has plans to build a 3 petaflop (3 x 10^15 FLOPS) machine by fall 2007, and a 10 petaflop machine in the 2010-2012 timeframe. More information on IBM's Blue Gene and other supercomputers can be found at http://www.top500.org/.

== Software Trends ==
With dramatic increases in hardware performance come more demanding applications, which in turn demand higher performance software. Many scientific applications available today, some even commercially, were not available on general purpose architectures even a few years ago.

'''Mathematica 6''' by Wolfram Research, is one of a growing number of commercially available scientific/engineering applications. Mathematica does not require multiple processors, but does require significant resources (at least, from the "average" personal computer) - at least 512mb memory. However, on many operating systems Mathematica is able to take advantage of multiple processors, particularly when doing linear algebra equations and dealing with machine-precision real numbers. Wolfram does offer a parallel computing toolkit (http://www.wolfram.com/products/applications/parallel) that allows Mathematica application designers to take advantage of various parallel architectures, ranging from shared memory multiprocessor machines to supercomputers. Wolfram also offers a version of Mathematica tailored to cluster/grid computing, see http://www.wolfram.com/products/gridmathematica/.

There is a trend in HPC towards '''virtualization'''. Virtualization allows application programmers to write applications for virtual machines, not concerning themselves with physical platforms. There are many benefits to running on virtual machines, among them the ability to seamlessly migrate the virtual machines (along with its running applications) off its physical host machine. However, in practice there are many challenges related to virtualization, chief among them the performance limitations they impose (http://www.scientificcomputing.com/ShowPR~PUBCODE~030~ACCT~3000000100~ISSUE~0707~RELTYPE~HPCC~PRODCODE~00000000~PRODLETT~C.html).

== Challenging Problems ==
Some problems are so complex that to solve them would require a significant increase (in some cases by orders of magnitude) in the current computational capabilities of today's computers. These problems are loosely defined as "Grand Challenge Problems." Grand Challenge problems are problems that are solvable, but not in a reasonable period of time on today's computers. Further, a Grand Challenge problem is a problem of some importance, either socially or economically.

Below are a sample of scientific/engineering applications that employ HPC. (Note: not all are classified as "Grand Challenge" problems, but all are challenging!)

'''Biology''' - Human Genome Project (HGP) (http://en.wikipedia.org/wiki/Human_genome_project).
The goal of the HGP is to "understand the genetic makeup of the human species." By some definitions of "complete sequencing" this work was completed in 2003. However, some work remains in that large area of the genome remain unsequenced. Some estimate the genome to be 92% sequenced. The remaining portions , highly repetitive sequences of DNA known as centromeres, are proving difficult with today's technology.

The basic approach to HGP is a classic "divide and conquer". The genome was broken down into smaller pieces, approximately 150,000 base pairs in length, processed separately, then assembled to form chromosones.

'''Physics''' Distributed and parallel computing is playing an increasing role in physics, including Particle Beam Physics. This paper (http://www.sciencedirect.com/science?_ob=ArticleURL&_udi=B6TJM-4B5R97X-3&_user=10&_coverDate=02%2F21%2F2004&_rdoc=1&_fmt=&_orig=search&_sort=d&view=c&_acct=C000050221&_version=1&_urlVersion=0&_userid=10&md5=721502408864d5addf95e432dfe4e0fe)
examines computational techniques in which cluster computing can be employed for a variety of beam physics problems.

The University of California at Santa Cruz uses a supercomputer to model supernova explosions, galaxy formation, and the fluid dynamics of the interiors of stars and planets. (http://www.unisci.com/stories/20021/0204026.htm)

'''Space Exploration''' - Search for Extraterrestrial Intelligence (SETI) (http://www.seti.org/). SETI's stated mission is to "explore, understand and explain the origin, nature and prevalence of life in the universe." The SETI@Home project (which is not an official project of SETI) uses CPU cycles from millions of computers to process data from the Arecibo Radio Telescope, in Puerto Rico. To take part in the project, users simply download and install a screensaver which, when activated, downloads and processes data, then uploads the results.

'''Weather Forecasting''' - Weather forecasting, a classic "supercomputer" problem, remains in the realm of supercomputers and will for the foreseeable future. Weather forecasting technology continues to improve, not only from increased hardware performance but also by improved software/modeling capabilities. Three day forecasts today are as accurate as one day forecast just 20 years ago (http://www.hpcwire.com/hpcwire/hpcwireWWW/04/0813/108178.html).

'''Game Playing''' - Checkers was solved by the program Chinook (http://www.cs.ualberta.ca/~chinook/project/) in March 2007, after over a decade of a dozen or more computers working nonstop on the problem. The search space for checkers is rather large - 5x10^20 nodes. (Chess is estimated at 10^44, which probably exceeds the number of molecules in the universe.) A number of research publications have emerged from the Chinook project (http://www.cs.ualberta.ca/~chinook/publications/research.html), including "APHID - Asynchronous Parallel Game Tree Search", and "Distributed Game-Tree Searching Using Transposition Table Driven Work Schedule."

CSC/ECE 506 Fall 2007/wiki1 2 3K8i

2007-09-05T14:59:47Z

Jfswaffo:

== Trends in Scientific and Engineering Computing ==

Scientific and engineering applications continue to demand the highest performance computers available, a trend established in the early days of supercomputers that continues today in the realm of "High Performance Computing" (HPC). Much work has been done in the areas of computational modeling and simulation. By using modeling, scientists are able to analyze hypothetical designs, rather than relying on empirical evidence, which is often difficult or impossible to come by. Higher performance computers afford the resources to build richer, more complicated models that allow scientists to study more difficult problems. As problems are solved, new, more complex problems arise to take their place. Many Grand Challenge Problems "on the radar" today were not feasible on the supercomputers of a just decade ago. Generally, each successive generation of Grand Challenge problems require more memory and faster processing capabilities. The architectures used to deliver those memory and processing speed requirements are changing, and along with them the algorithms and techniques used to make efficient use of them.

Before looking at some of today's most challenging computational problems, it may be instructive to look at the trends in HPC over the last decade or so.

== Hardware Trends ==
According the the U.S. Army Research Laboratory (http://www.arl.army.mil/www/default.cfm?Action=20&Page=272), there have been five generations of architectures in the realm of scientific computing. They are serial processors (1947-1986), vector processors (1986-2002), shared memory (1993-present), distributed memory (2000-present), and commodity clusters (2001-present).

Indeed, the trend in recent years in multiprocessing has been away from vector architectures and towards low cost, multi-threaded single address spaced systems. (http://www.nus.edu.sg/comcen/svu/publications/SVULink/vol_1_iss_1/hpc-trends.html) Multi-core processors are becoming more and more mainstream. Today, many new desktop systems contain dual cores, with some quad cores being sold. Tony Hey (http://en.wikipedia.org/wiki/Tony_Hey), a leading researcher in parallel computing, has predicted that by 2015, a single socket will contain hundreds of cores. (http://www.accessmylibrary.com/coms2/summary_0286-30177016_ITM)

There have also been strong trends towards cluster and grid computing, which seek to take advantage of multiple, low cost (commodity) computer systems and treat them as a logical entity. Several categories of clusters exists, ranging from high performance computers linked together via high speed interconnects, to geographically separated systems linked together over the Internet. (http://en.wikipedia.org/wiki/Cluster_computing) Grid computing is a form of the latter, generally composed of multiple "collections" of computers (grid elements) that do not necessarily trust each other.

Putting these together, we see a clear movement towards commodity processors in both the areas of parallel computing (processors in a single computer system) and distributed computing (using multiple computer systems). Perhaps the strongest driving force behind these trends is one of supply and demand, or economies of scale. Specialized hardware is, by definition, in less demand then general purpose hardware, making it much more difficult to recover design and production costs. Hence, there is a strong economic incentive for consumers and manufacturers alike to favor more general purpose solutions.

Despite these trends, the "traditional" supercomputer is alive and well. Today's highest performance machines are capable of performing hundreds of teraflops per second. (A teraflop is 1 x 10^12 FLOPS.) As of June 2007, the world's fastest computer, as measured by the Linpack (http://en.wikipedia.org/wiki/Linpack) benchmark, is IBM's massively parallel Blue Gene/L. IBM has plans to build a 3 petaflop (3 x 10^15 FLOPS) machine by fall 2007, and a 10 petaflop machine in the 2010-2012 timeframe. More information on IBM's Blue Gene and other supercomputers can be found at http://www.top500.org/.

== Software Trends ==
With dramatic increases in hardware performance come more demanding applications, which in turn demand higher performance software. Many scientific applications available today, some even commercially, were not available on general purpose architectures even a few years ago.

'''Mathematica 6''' by Wolfram Research, is one of a growing number of commercially available scientific/engineering applications. Mathematica does not require multiple processors, but does require significant resources (at least, from the "average" personal computer) - at least 512mb memory. However, on many operating systems Mathematica is able to take advantage of multiple processors, particularly when doing linear algebra equations and dealing with machine-precision real numbers. Wolfram does offer a parallel computing toolkit (http://www.wolfram.com/products/applications/parallel) that allows Mathematica application designers to take advantage of various parallel architectures, ranging from shared memory multiprocessor machines to supercomputers. Wolfram also offers a version of Mathematica tailored to cluster/grid computing, see http://www.wolfram.com/products/gridmathematica/.

There is a trend in HPC towards '''virtualization'''. Virtualization allows application programmers to write applications for virtual machines, not concerning themselves with physical platforms. There are many benefits to running on virtual machines, among them the ability to seamlessly migrate the virtual machines (along with its running applications) off its physical host machine. However, in practice there are many challenges related to virtualization, chief among them the performance limitations they impose (http://www.scientificcomputing.com/ShowPR~PUBCODE~030~ACCT~3000000100~ISSUE~0707~RELTYPE~HPCC~PRODCODE~00000000~PRODLETT~C.html).

== Challenging Problems ==
Some problems are so complex that to solve them would require a significant increase (in some cases by orders of magnitude) in the current computational capabilities of today's computers. These problems are loosely defined as "Grand Challenge Problems." Grand Challenge problems are problems that are solvable, but not in a reasonable period of time on today's computers. Further, a Grand Challenge problem is a problem of some importance, either socially or economically.

Below are a sample of scientific/engineering applications that employ HPC. (Note: not all are classified as "Grand Challenge" problems, but all are challenging!)

'''Biology''' - Human Genome Project (HGP) (http://en.wikipedia.org/wiki/Human_genome_project).
The goal of the HGP is to "understand the genetic makeup of the human species." By some definitions of "complete sequencing" this work was completed in 2003. However, some work remains in that large area of the genome remain unsequenced. Some estimate the genome to be 92% sequenced. The remaining portions , highly repetitive sequences of DNA known as centromeres, are proving difficult with today's technology.

The basic approach to HGP is a classic "divide and conquer". The genome was broken down into smaller pieces, approximately 150,000 base pairs in length, processed separately, then assembled to form chromosones.

'''Physics''' Distributed and parallel computing is playing an increasing role in physics, including Particle Beam Physics. This paper (http://www.sciencedirect.com/science?_ob=ArticleURL&_udi=B6TJM-4B5R97X-3&_user=10&_coverDate=02%2F21%2F2004&_rdoc=1&_fmt=&_orig=search&_sort=d&view=c&_acct=C000050221&_version=1&_urlVersion=0&_userid=10&md5=721502408864d5addf95e432dfe4e0fe)
examines computational techniques in which cluster computing can be employed for a variety of beam physics problems.

The University of California at Santa Cruz uses a supercomputer to model supernova explosions, galaxy formation, and the fluid dynamics of the interiors of stars and planets. (http://www.unisci.com/stories/20021/0204026.htm)

'''Space Exploration''' - Search for Extraterrestrial Intelligence (SETI) (http://www.seti.org/). SETI's stated mission is to "explore, understand and explain the origin, nature and prevalence of life in the universe." The SETI@Home project (which is not an official project of SETI) uses CPU cycles from millions of computers to process data from the Arecibo Radio Telescope, in Puerto Rico. To take part in the project, users simply download and install a screensaver which, when activated, downloads and processes data, then uploads the results.

'''Weather Forecasting''' - Weather forecasting, a classic "supercomputer" problem, remains in the realm of supercomputers and will for the foreseeable future. Weather forecasting technology continues to improve, not only from increased hardware performance but also by improved software/modeling capabilities. Three day forecasts today are as accurate as one day forecast just 20 years ago (http://www.hpcwire.com/hpcwire/hpcwireWWW/04/0813/108178.html).

'''Game Playing''' - Checkers was solved by the program Chinook (http://www.cs.ualberta.ca/~chinook/project/) in March 2007, after over a decade of a dozen or more computers working nonstop on the problem. The search space for checkers is rather large - 5x10^20 nodes. (Chess is estimated at 10^44, which probably exceeds the number of molecules in the universe.) A number of research publications have emerged from the Chinook project (http://www.cs.ualberta.ca/~chinook/publications/research.html), including "APHID - Asynchronous Parallel Game Tree Search", and "Distributed Game-Tree Searching Using Transposition Table Driven Work Schedule."

CSC/ECE 506 Fall 2007/wiki1 2 3K8i

2007-09-05T14:51:09Z

Jfswaffo:

== Trends in Scientific and Engineering Computing ==

Scientific and engineering applications continue to demand the highest performance computers available, a trend established in the early days of supercomputers that continues today in the realm of "High Performance Computing" (HPC). Much work has been done in the areas of computational modeling and simulation. By using modeling, scientists are able to analyze hypothetical designs, rather than relying on empirical evidence, which is often difficult or impossible to come by. Higher performance computers afford the resources to build richer, more complicated models that allow scientists to study more difficult problems. As problems are solved, new, more complex problems arise to take their place. Many Grand Challenge Problems "on the radar" today were not feasible on the supercomputers of a just decade ago. Generally, each successive generation of Grand Challenge problems require more memory and faster processing capabilities. The architectures used to deliver those memory and processing speed requirements are changing, and along with them the algorithms and techniques used to make efficient use of them.

Before looking at some of today's most challenging computational problems, it may be instructive to look at the trends in HPC over the last decade or so.

== Hardware Trends ==
According the the U.S. Army Research Laboratory (http://www.arl.army.mil/www/default.cfm?Action=20&Page=272), there have been five generations of architectures in the realm of scientific computing. They are serial processors (1947-1986), vector processors (1986-2002), shared memory (1993-present), distributed memory (2000-present), and commodity clusters (2001-present).

Indeed, the trend in recent years in multiprocessing has been away from vector architectures and towards low cost, multi-threaded single address spaced systems. (http://www.nus.edu.sg/comcen/svu/publications/SVULink/vol_1_iss_1/hpc-trends.html) Multi-core processors are becoming more and more mainstream. Today, many new desktop systems contain dual cores, with some quad cores being sold. Tony Hey (http://en.wikipedia.org/wiki/Tony_Hey), a leading researcher in parallel computing, has predicted that by 2015, a single socket will contain hundreds of cores. (http://www.accessmylibrary.com/coms2/summary_0286-30177016_ITM)

There have also been strong trends towards cluster and grid computing, which seek to take advantage of multiple, low cost (commodity) computer systems and treat them as a logical entity. Several categories of clusters exists, ranging from high performance computers linked together via high speed interconnects, to geographically separated systems linked together over the Internet. (http://en.wikipedia.org/wiki/Cluster_computing) Grid computing is a form of the latter, generally composed of multiple "collections" of computers (grid elements) that do not necessarily trust each other.

Putting these together, we see a clear movement towards commodity processors in both the areas of parallel computing (processors in a single computer system) and distributed computing (using multiple computer systems). Perhaps the strongest driving force behind these trends is one of supply and demand, or economies of scale. Specialized hardware is, by definition, in less demand then general purpose hardware, making it much more difficult to recover design and production costs. Hence, there is a strong economic incentive for consumers and manufacturers alike to favor more general purpose solutions.

Despite these trends, the "traditional" supercomputer is alive and well. Today's highest performance machines are capable of performing hundreds of teraflops per second. (A teraflop is 1 x 10^12 FLOPS.) As of June 2007, the world's fastest computer, as measured by the Linpack (http://en.wikipedia.org/wiki/Linpack) benchmark, is IBM's massively parallel Blue Gene/L. IBM has plans to build a 3 petaflop (3 x 10^15 FLOPS) machine by fall 2007, and a 10 petaflop machine in the 2010-2012 timeframe. More information on IBM's Blue Gene and other supercomputers can be found at http://www.top500.org/.

== Software Trends ==
With dramatic increases in hardware performance come more demanding applications, which in turn demand higher performance software. Many scientific applications available today, some even commercially, were not available on general purpose architectures even a few years ago.

'''Mathematica 6''' by Wolfram Research, is one of a growing number of commercially available scientific/engineering applications. Mathematica does not require multiple processors, but does require significant resources (at least, from the "average" personal computer) - at least 512mb memory. However, on many operating systems Mathematica is able to take advantage of multiple processors, particularly when doing linear algebra equations and dealing with machine-precision real numbers. Wolfram does offer a parallel computing toolkit (http://www.wolfram.com/products/applications/parallel) that allows Mathematica application designers to take advantage of various parallel architectures, ranging from shared memory multiprocessor machines to supercomputers. Wolfram also offers a version of Mathematica tailored to cluster/grid computing, see http://www.wolfram.com/products/gridmathematica/.

There is a trend in HPC towards '''virtualization'''. Virtualization allows application programmers to write applications for virtual machines, not concerning themselves with physical platforms. There are many benefits to running on virtual machines, among them the ability to seamlessly migrate the virtual machines (along with its running applications) off its physical host machine. However, in practice there are many challenges related to virtualization, chief among them the performance limitations they impose (http://www.scientificcomputing.com/ShowPR~PUBCODE~030~ACCT~3000000100~ISSUE~0707~RELTYPE~HPCC~PRODCODE~00000000~PRODLETT~C.html).

== Challenging Problems ==
Some problems are so complex that to solve them would require a significant increase (in some cases by orders of magnitude) in the current computational capabilities of today's computers. These problems are loosely defined as "Grand Challenge Problems." Grand Challenge problems are problems that are solvable, but not in a reasonable period of time on today's computers. Further, a Grand Challenge problem is a problem of some importance, either socially or economically.

Below are a sample of scientific/engineering applications that employ HPC. (Note: not all are classified as "Grand Challenge" problems, but all are challenging!)

'''Biology''' - Human Genome Project (HGP) (http://en.wikipedia.org/wiki/Human_genome_project).
The goal of the HGP is to "understand the genetic makeup of the human species." By some definitions of "complete sequencing" this work was completed in 2003. However, some work remains in that large area of the genome remain unsequenced. Some estimate the genome to be 92% sequenced. The remaining portions , highly repetitive sequences of DNA known as centromeres, are proving difficult with today's technology.

The basic approach to HGP is a classic "divide and conquer". The genome was broken down into smaller pieces, approximately 150,000 base pairs in length, processed separately, then assembled to form chromosones.

'''Physics''' Distributed and parallel computing is playing an increasing role in physics, including Particle Beam Physics. This paper (http://www.sciencedirect.com/science?_ob=ArticleURL&_udi=B6TJM-4B5R97X-3&_user=10&_coverDate=02%2F21%2F2004&_rdoc=1&_fmt=&_orig=search&_sort=d&view=c&_acct=C000050221&_version=1&_urlVersion=0&_userid=10&md5=721502408864d5addf95e432dfe4e0fe)
examines computational techniques in which cluster computing can be employed for a variety of beam physics problems.

The University of California at Santa Cruz uses a supercomputer to model supernova explosions, galaxy formation, and the fluid dynamics of the interiors of stars and planets. (http://www.unisci.com/stories/20021/0204026.htm)

'''Space Exploration''' - Search for Extraterrestrial Intelligence (SETI) (http://www.seti.org/). SETI's stated mission is to "explore, understand and explain the origin, nature and prevalence of life in the universe." The SETI@Home project (which is not an official project of SETI) uses CPU cycles from millions of computers to process data from the Arecibo Radio Telescope, in Puerto Rico. To take part in the project, users simply download and install a screensaver which, when activated, downloads and processes data, then uploads the results.

'''Cognition/Strong AI''' - the idea that computers can become "self aware." (vs. weak AI who's goal is not so grandiose - Turing test)

'''Game Playing''' - Checkers was solved by the program Chinook (http://www.cs.ualberta.ca/~chinook/project/) in March 2007, after over a decade of a dozen or more computers working nonstop on the problem. The search space for checkers is rather large - 5x10^20 nodes. (Chess is estimated at 10^44, which probably exceeds the number of molecules in the universe.) A number of research publications have emerged from the Chinook project (http://www.cs.ualberta.ca/~chinook/publications/research.html), including "APHID - Asynchronous Parallel Game Tree Search", and "Distributed Game-Tree Searching Using Transposition Table Driven Work Schedule."

CSC/ECE 506 Fall 2007/wiki1 2 3K8i

2007-09-05T14:39:22Z

Jfswaffo:

== Trends in Scientific and Engineering Computing ==

Scientific and engineering applications continue to demand the highest performance computers available, a trend established in the early days of supercomputers that continues today in the realm of "High Performance Computing" (HPC). Much work has been done in the areas of computational modeling and simulation. By using modeling, scientists are able to analyze hypothetical designs, rather than relying on empirical evidence, which is often difficult or impossible to come by. Higher performance computers afford the resources to build richer, more complicated models that allow scientists to study more difficult problems. As problems are solved, new, more complex problems arise to take their place. Many Grand Challenge Problems "on the radar" today were not feasible on the supercomputers of a just decade ago. Generally, each successive generation of Grand Challenge problems require more memory and faster processing capabilities. The architectures used to deliver those memory and processing speed requirements are changing, and along with them the algorithms and techniques used to make efficient use of them.

Before looking at some of today's most challenging computational problems, it may be instructive to look at the trends in HPC over the last decade or so.

== Hardware Trends ==
According the the U.S. Army Research Laboratory (http://www.arl.army.mil/www/default.cfm?Action=20&Page=272), there have been five generations of architectures in the realm of scientific computing. They are serial processors (1947-1986), vector processors (1986-2002), shared memory (1993-present), distributed memory (2000-present), and commodity clusters (2001-present).

Indeed, the trend in recent years in multiprocessing has been away from vector architectures and towards low cost, multi-threaded single address spaced systems. (http://www.nus.edu.sg/comcen/svu/publications/SVULink/vol_1_iss_1/hpc-trends.html) Multi-core processors are becoming more and more mainstream. Today, many new desktop systems contain dual cores, with some quad cores being sold. Tony Hey (http://en.wikipedia.org/wiki/Tony_Hey), a leading researcher in parallel computing, has predicted that by 2015, a single socket will contain hundreds of cores. (http://www.accessmylibrary.com/coms2/summary_0286-30177016_ITM)

There have also been strong trends towards cluster and grid computing, which seek to take advantage of multiple, low cost (commodity) computer systems and treat them as a logical entity. Several categories of clusters exists, ranging from high performance computers linked together via high speed interconnects, to geographically separated systems linked together over the Internet. (http://en.wikipedia.org/wiki/Cluster_computing) Grid computing is a form of the latter, generally composed of multiple "collections" of computers (grid elements) that do not necessarily trust each other.

Putting these together, we see a clear movement towards commodity processors in both the areas of parallel computing (processors in a single computer system) and distributed computing (using multiple computer systems). Perhaps the strongest driving force behind these trends is one of supply and demand, or economies of scale. Specialized hardware is, by definition, in less demand then general purpose hardware, making it much more difficult to recover design and production costs. Hence, there is a strong economic incentive for consumers and manufacturers alike to favor more general purpose solutions.

Despite these trends, the "traditional" supercomputer is alive and well. Today's highest performance machines are capable of performing hundreds of teraflops per second. (A teraflop is 1 x 10^12 FLOPS.) As of June 2007, the world's fastest computer, as measured by the Linpack (http://en.wikipedia.org/wiki/Linpack) benchmark, is IBM's massively parallel Blue Gene/L. IBM has plans to build a 3 petaflop (3 x 10^15 FLOPS) machine by fall 2007, and a 10 petaflop machine in the 2010-2012 timeframe. More information on IBM's Blue Gene and other supercomputers can be found at http://www.top500.org/.

== Software Trends ==
With dramatic increases in hardware performance come more demanding applications, which in turn demand higher performance software. Many scientific applications available today, some even commercially, were not available on general purpose architectures even a few years ago.

'''Mathematica 6''' by Wolfram Research, is one of a growing number of commercially available scientific/engineering applications. Mathematica does not require multiple processors, but does require significant resources (at least, from the "average" personal computer) - at least 512mb memory. However, on many operating systems Mathematica is able to take advantage of multiple processors, particularly when doing linear algebra equations and dealing with machine-precision real numbers. Wolfram does offer a parallel computing toolkit (http://www.wolfram.com/products/applications/parallel) that allows Mathematica application designers to take advantage of various parallel architectures, ranging from shared memory multiprocessor machines to supercomputers. Wolfram also offers a version of Mathematica tailored to cluster/grid computing, see http://www.wolfram.com/products/gridmathematica/.

There is a trend in HPC towards '''virtualization'''. Virtualization allows application programmers to write applications for virtual machines, not concerning themselves with physical platforms. There are many benefits to running on virtual machines, among them the ability to seamlessly migrate the virtual machines (along with its running applications) off its physical host machine. However, in practice there are many challenges related to virtualization, chief among them the performance limitations they impose (http://www.scientificcomputing.com/ShowPR~PUBCODE~030~ACCT~3000000100~ISSUE~0707~RELTYPE~HPCC~PRODCODE~00000000~PRODLETT~C.html).

== Challenging Problems ==
Some problems are so complex that to solve them would require a significant increase (in some cases by orders of magnitude) in the current computational capabilities of today's computers. These problems are loosely defined as "Grand Challenge Problems." Grand Challenge problems are problems that are solvable, but not in a reasonable period of time on today's computers. Further, a Grand Challenge problem is a problem of some importance, either socially or economically.

Below are a sample of scientific/engineering applications that employ HPC. (Note: not all are classified as "Grand Challenge" problems, but all are challenging!)

'''Biology''' - Human Genome Project (HGP) (http://en.wikipedia.org/wiki/Human_genome_project).
The goal of the HGP is to "understand the genetic makeup of the human species." By some definitions of "complete sequencing" this work was completed in 2003. However, some work remains in that large area of the genome remain unsequenced. Some estimate the genome to be 92% sequenced. The remaining portions , highly repetitive sequences of DNA known as centromeres, are proving difficult with today's technology.

The basic approach to HGP is a classic "divide and conquer". The genome was broken down into smaller pieces, approximately 150,000 base pairs in length, processed separately, then assembled to form chromosones.

'''Physics''' (nuclear technology)

'''Space Exploration''' - Search for Extraterrestrial Intelligence (SETI) (http://www.seti.org/). SETI's stated mission is to "explore, understand and explain the origin, nature and prevalence of life in the universe." The SETI@Home project (which is not an official project of SETI) uses CPU cycles from millions of computers to process data from the Arecibo Radio Telescope, in Puerto Rico. To take part in the project, users simply download and install a screensaver which, when activated, downloads and processes data, then uploads the results.

'''Cognition/Strong AI''' - the idea that computers can become "self aware." (vs. weak AI who's goal is not so grandiose - Turing test)

'''Game Playing''' - Checkers was solved by the program Chinook (http://www.cs.ualberta.ca/~chinook/project/) in March 2007, after over a decade of a dozen or more computers working nonstop on the problem. The search space for checkers is rather large - 5x10^20 nodes. (Chess is estimated at 10^44, which probably exceeds the number of molecules in the universe.) A number of research publications have emerged from the Chinook project (http://www.cs.ualberta.ca/~chinook/publications/research.html), including "APHID - Asynchronous Parallel Game Tree Search", and "Distributed Game-Tree Searching Using Transposition Table Driven Work Schedule."

CSC/ECE 506 Fall 2007/wiki1 2 3K8i

2007-09-05T14:26:45Z

Jfswaffo:

== Trends in Scientific and Engineering Computing ==

Scientific and engineering applications continue to demand the highest performance computers available, a trend established in the early days of supercomputers that continues today in the realm of "High Performance Computing" (HPC). Much work has been done in the areas of computational modeling and simulation. By using modeling, scientists are able to analyze hypothetical designs, rather than relying on empirical evidence, which is often difficult or impossible to come by. Higher performance computers afford the resources to build richer, more complicated models that allow scientists to study more difficult problems. As problems are solved, new, more complex problems arise to take their place. Many Grand Challenge Problems "on the radar" today were not feasible on the supercomputers of a just decade ago. Generally, each successive generation of Grand Challenge problems require more memory and faster processing capabilities. The architectures used to deliver those memory and processing speed requirements are changing, and along with them the algorithms and techniques used to make efficient use of them.

Before looking at some of today's most challenging computational problems, it may be instructive to look at the trends in HPC over the last decade or so.

== Hardware Trends ==
According the the U.S. Army Research Laboratory (http://www.arl.army.mil/www/default.cfm?Action=20&Page=272), there have been five generations of architectures in the realm of scientific computing. They are serial processors (1947-1986), vector processors (1986-2002), shared memory (1993-present), distributed memory (2000-present), and commodity clusters (2001-present).

Indeed, the trend in recent years in multiprocessing has been away from vector architectures and towards low cost, multi-threaded single address spaced systems. (http://www.nus.edu.sg/comcen/svu/publications/SVULink/vol_1_iss_1/hpc-trends.html) Multi-core processors are becoming more and more mainstream. Today, many new desktop systems contain dual cores, with some quad cores being sold. Tony Hey (http://en.wikipedia.org/wiki/Tony_Hey), a leading researcher in parallel computing, has predicted that by 2015, a single socket will contain hundreds of cores. (http://www.accessmylibrary.com/coms2/summary_0286-30177016_ITM)

There have also been strong trends towards cluster and grid computing, which seek to take advantage of multiple, low cost (commodity) computer systems and treat them as a logical entity. Several categories of clusters exists, ranging from high performance computers linked together via high speed interconnects, to geographically separated systems linked together over the Internet. (http://en.wikipedia.org/wiki/Cluster_computing) Grid computing is a form of the latter, generally composed of multiple "collections" of computers (grid elements) that do not necessarily trust each other.

Putting these together, we see a clear movement towards commodity processors in both the areas of parallel computing (processors in a single computer system) and distributed computing (using multiple computer systems). Perhaps the strongest driving force behind these trends is one of supply and demand, or economies of scale. Specialized hardware is, by definition, in less demand then general purpose hardware, making it much more difficult to recover design and production costs. Hence, there is a strong economic incentive for consumers and manufacturers alike to favor more general purpose solutions.

Despite these trends, the "traditional" supercomputer is alive and well. Today's highest performance machines are capable of performing hundreds of teraflops per second. (A teraflop is 1 x 10^12 FLOPS.) As of June 2007, the world's fastest computer, as measured by the Linpack (http://en.wikipedia.org/wiki/Linpack) benchmark, is IBM's massively parallel Blue Gene/L. IBM has plans to build a 3 petaflop (3 x 10^15 FLOPS) machine by fall 2007, and a 10 petaflop machine in the 2010-2012 timeframe. More information on IBM's Blue Gene and other supercomputers can be found at http://www.top500.org/.

== Software Trends ==
With dramatic increases in hardware performance come more demanding applications, which in turn demand higher performance software. Many scientific applications available today, some even commercially, were not available on general purpose architectures even a few years ago.

'''Mathematica 6''' by Wolfram Research, is one of a growing number of commercially available scientific/engineering applications. Mathematica does not require multiple processors, but does require significant resources (at least, from the "average" personal computer) - at least 512mb memory. However, on many operating systems Mathematica is able to take advantage of multiple processors, particularly when doing linear algebra equations and dealing with machine-precision real numbers. Wolfram does offer a parallel computing toolkit (http://www.wolfram.com/products/applications/parallel) that allows Mathematica application designers to take advantage of various parallel architectures, ranging from shared memory multiprocessor machines to supercomputers. Wolfram also offers a version of Mathematica tailored to cluster/grid computing, see http://www.wolfram.com/products/gridmathematica/.

There is a trend in HPC towards '''virtualization'''. Virtualization allows application programmers to write applications for virtual machines, not concerning themselves with physical platforms. There are many benefits to running on virtual machines, among them the ability to seamlessly migrate the virtual machines (along with its running applications) off its physical host machine. However, in practice there are many challenges related to virtualization, chief among them the performance limitations they impose (http://www.scientificcomputing.com/ShowPR~PUBCODE~030~ACCT~3000000100~ISSUE~0707~RELTYPE~HPCC~PRODCODE~00000000~PRODLETT~C.html).

== Challenging Problems ==
Some problems are so complex that to solve them would require a significant increase (in some cases by orders of magnitude) in the current computational capabilities of today's computers. These problems are loosely defined as "Grand Challenge Problems." Grand Challenge problems are problems that are solvable, but not in a reasonable period of time on today's computers. Further, a Grand Challenge problem is a problem of some importance, either socially or economically.

Below are a sample of scientific/engineering applications that employ HPC. (Note: not all are classified as "Grand Challenge" problems, but all are challenging!)

'''Biology''' - Human Genome Project (HGP) (http://en.wikipedia.org/wiki/Human_genome_project).
The goal of the HGP is to "understand the genetic makeup of the human species." By some definitions of "complete sequencing" this work was completed in 2003. However, some work remains in that large area of the genome remain unsequenced. Some estimate the genome to be 92% sequenced. The remaining portions , highly repetitive sequences of DNA known as centromeres, are proving difficult with today's technology.

The basic approach to HGP is a classic "divide and conquer". The genome was broken down into smaller pieces, approximately 150,000 base pairs in length, processed separately, then assembled to form chromosones.

'''Physics''' (nuclear technology)

'''Astronomy'''

'''Cognition/Strong AI''' - the idea that computers can become "self aware." (vs. weak AI who's goal is not so grandiose - Turing test)

'''Game Playing''' - Checkers was solved by the program Chinook (http://www.cs.ualberta.ca/~chinook/project/) in March 2007, after over a decade of a dozen or more computers working nonstop on the problem. The search space for checkers is rather large - 5x10^20 nodes. (Chess is estimated at 10^44, which probably exceeds the number of molecules in the universe.) A number of research publications have emerged from the Chinook project (http://www.cs.ualberta.ca/~chinook/publications/research.html), including "APHID - Asynchronous Parallel Game Tree Search", and "Distributed Game-Tree Searching Using Transposition Table Driven Work Schedule."

CSC/ECE 506 Fall 2007/wiki1 2 3K8i

2007-09-05T14:16:43Z

Jfswaffo:

== Trends in Scientific and Engineering Computing ==

Scientific and engineering applications continue to demand the highest performance computers available, a trend established in the early days of supercomputers that continues today in the realm of "High Performance Computing" (HPC). Much work has been done in the areas of computational modeling and simulation. By using modeling, scientists are able to analyze hypothetical designs, rather than relying on empirical evidence, which is often difficult or impossible to come by. Higher performance computers afford the resources to build richer, more complicated models that allow scientists to study more difficult problems. As problems are solved, new, more complex problems arise to take their place. Many Grand Challenge Problems "on the radar" today were not feasible on the supercomputers of a just decade ago. Generally, each successive generation of Grand Challenge problems require more memory and faster processing capabilities. The architectures used to deliver those memory and processing speed requirements are changing, and along with them the algorithms and techniques used to make efficient use of them.

Before looking at some of today's most challenging computational problems, it may be instructive to look at the trends in HPC over the last decade or so.

== Hardware Trends ==
According the the U.S. Army Research Laboratory (http://www.arl.army.mil/www/default.cfm?Action=20&Page=272), there have been five generations of architectures in the realm of scientific computing. They are serial processors (1947-1986), vector processors (1986-2002), shared memory (1993-present), distributed memory (2000-present), and commodity clusters (2001-present).

Indeed, the trend in recent years in multiprocessing has been away from vector architectures and towards low cost, multi-threaded single address spaced systems. (http://www.nus.edu.sg/comcen/svu/publications/SVULink/vol_1_iss_1/hpc-trends.html) Multi-core processors are becoming more and more mainstream. Today, many new desktop systems contain dual cores, with some quad cores being sold. Tony Hey (http://en.wikipedia.org/wiki/Tony_Hey), a leading researcher in parallel computing, has predicted that by 2015, a single socket will contain hundreds of cores. (http://www.accessmylibrary.com/coms2/summary_0286-30177016_ITM)

There have also been strong trends towards cluster and grid computing, which seek to take advantage of multiple, low cost (commodity) computer systems and treat them as a logical entity. Several categories of clusters exists, ranging from high performance computers linked together via high speed interconnects, to geographically separated systems linked together over the Internet. (http://en.wikipedia.org/wiki/Cluster_computing) Grid computing is a form of the latter, generally composed of multiple "collections" of computers (grid elements) that do not necessarily trust each other.

Putting these together, we see a clear movement towards commodity processors in both the areas of parallel computing (processors in a single computer system) and distributed computing (using multiple computer systems). Perhaps the strongest driving force behind these trends is one of supply and demand, or economies of scale. Specialized hardware is, by definition, in less demand then general purpose hardware, making it much more difficult to recover design and production costs. Hence, there is a strong economic incentive for consumers and manufacturers alike to favor more general purpose solutions.

Despite these trends, the "traditional" supercomputer is alive and well. Today's highest performance machines are capable of performing hundreds of teraflops per second. (A teraflop is 1 x 10^12 FLOPS.) As of June 2007, the world's fastest computer, as measured by the Linpack (http://en.wikipedia.org/wiki/Linpack) benchmark, is IBM's massively parallel Blue Gene/L. IBM has plans to build a 3 petaflop (3 x 10^15 FLOPS) machine by fall 2007, and a 10 petaflop machine in the 2010-2012 timeframe. More information on IBM's Blue Gene and other supercomputers can be found at http://www.top500.org/.

== Software Trends ==
With dramatic increases in hardware performance come more demanding applications, which in turn demand higher performance software. Many scientific applications available today, some even commercially, were not available on general purpose architectures even a few years ago.

'''Mathematica 6''' by Wolfram Research, is one of a growing number of commercially available scientific/engineering applications. Mathematica does not require multiple processors, but does require significant resources (at least, from the "average" personal computer) - at least 512mb memory. However, on many operating systems Mathematica is able to take advantage of multiple processors, particularly when doing linear algebra equations and dealing with machine-precision real numbers. Wolfram does offer a parallel computing toolkit (http://www.wolfram.com/products/applications/parallel) that allows Mathematica application designers to take advantage of various parallel architectures, ranging from shared memory multiprocessor machines to supercomputers. Wolfram also offers a version of Mathematica tailored to cluster/grid computing, see http://www.wolfram.com/products/gridmathematica/.

There is a trend in HPC towards '''virtualization'''. Virtualization allows application programmers to write applications for virtual machines, not concerning themselves with physical platforms. There are many benefits to running on virtual machines, among them the ability to seamlessly migrate the virtual machines (along with its running applications) off its physical host machine. However, in practice there are many challenges related to virtualization, chief among them the performance limitations they impose (http://www.scientificcomputing.com/ShowPR~PUBCODE~030~ACCT~3000000100~ISSUE~0707~RELTYPE~HPCC~PRODCODE~00000000~PRODLETT~C.html).

== Challenging Problems ==
Some problems are so complex that to solve them would require a significant increase (in some cases by orders of magnitude) in the current computational capabilities of today's computers. These problems are loosely defined as "Grand Challenge Problems." Grand Challenge problems are problems that are solvable, but not in a reasonable period of time on today's computers. Further, a Grand Challenge problem is a problem of some importance, either socially or economically.

Below are a sample of scientific/engineering applications that employ HPC. (Note: not all are "Grand Challenge" problems, but all are challenging!)

'''Biology''' - Human Genome Project (HGP) (http://en.wikipedia.org/wiki/Human_genome_project).
The goal of the HGP is to "understand the genetic makeup of the human species." By some definitions of "complete sequencing" this work was completed in 2003. However, some work remains in that large area of the genome remain unsequenced. Some estimate the genome to be 92% sequenced. The remaining portions , highly repetitive sequences of DNA known as centromeres, are proving difficult with today's technology.

The basic approach to HGP is a classic "divide and conquer". The genome was broken down into smaller pieces, approximately 150,000 base pairs in length, processed separately, then assembled to form chromosones.

'''Physics''' (nuclear technology)

'''Astronomy'''

'''Cognition/Strong AI''' - the idea that computers can become "self aware." (vs. weak AI who's goal is not so grandiose - Turing test)

CSC/ECE 506 Fall 2007/wiki1 2 3K8i

2007-09-05T14:13:45Z

Jfswaffo:

== Trends in Scientific and Engineering Computing ==

Scientific and engineering applications continue to demand the highest performance computers available, a trend established in the early days of supercomputers that continues today in the realm of "High Performance Computing" (HPC). Much work has been done in the areas of computational modeling and simulation. By using modeling, scientists are able to analyze hypothetical designs, rather than relying on empirical evidence, which is often difficult or impossible to come by. Higher performance computers afford the resources to build richer, more complicated models that allow scientists to study more difficult problems. As problems are solved, new, more complex problems arise to take their place. Many Grand Challenge Problems "on the radar" today were not feasible on the supercomputers of a just decade ago. Generally, each successive generation of Grand Challenge problems require more memory and faster processing capabilities. The architectures used to deliver those memory and processing speed requirements are changing, and along with them the algorithms and techniques used to make efficient use of them.

Before looking at some of today's most challenging computational problems, it may be instructive to look at the trends in HPC over the last decade or so.

== Hardware Trends ==
According the the U.S. Army Research Laboratory (http://www.arl.army.mil/www/default.cfm?Action=20&Page=272), there have been five generations of architectures in the realm of scientific computing. They are serial processors (1947-1986), vector processors (1986-2002), shared memory (1993-present), distributed memory (2000-present), and commodity clusters (2001-present).

Indeed, the trend in recent years in multiprocessing has been away from vector architectures and towards low cost, multi-threaded single address spaced systems. (http://www.nus.edu.sg/comcen/svu/publications/SVULink/vol_1_iss_1/hpc-trends.html) Multi-core processors are becoming more and more mainstream. Today, many new desktop systems contain dual cores, with some quad cores being sold. Tony Hey (http://en.wikipedia.org/wiki/Tony_Hey), a leading researcher in parallel computing, has predicted that by 2015, a single socket will contain hundreds of cores. (http://www.accessmylibrary.com/coms2/summary_0286-30177016_ITM)

There have also been strong trends towards cluster and grid computing, which seek to take advantage of multiple, low cost (commodity) computer systems and treat them as a logical entity. Several categories of clusters exists, ranging from high performance computers linked together via high speed interconnects, to geographically separated systems linked together over the Internet. (http://en.wikipedia.org/wiki/Cluster_computing) Grid computing is a form of the latter, generally composed of multiple "collections" of computers (grid elements) that do not necessarily trust each other.

Putting these together, we see a clear movement towards commodity processors in both the areas of parallel computing (processors in a single computer system) and distributed computing (using multiple computer systems). Perhaps the strongest driving force behind these trends is one of supply and demand, or economies of scale. Specialized hardware is, by definition, in less demand then general purpose hardware, making it much more difficult to recover design and production costs. Hence, there is a strong economic incentive for consumers and manufacturers alike to favor more general purpose solutions.

Despite these trends, the "traditional" supercomputer is alive and well. Today's highest performance machines are capable of performing hundreds of teraflops per second. (A teraflop is 1 x 10^12 FLOPS.) As of June 2007, the world's fastest computer, as measured by the Linpack (http://en.wikipedia.org/wiki/Linpack) benchmark, is IBM's massively parallel Blue Gene/L. IBM has plans to build a 3 petaflop (3 x 10^15 FLOPS) machine by fall 2007, and a 10 petaflop machine in the 2010-2012 timeframe. More information on IBM's Blue Gene and other supercomputers can be found at http://www.top500.org/.

== Software Trends ==
With dramatic increases in hardware performance come more demanding applications, which in turn demand higher performance software. Many scientific applications available today, some even commercially, were not available on general purpose architectures even a few years ago.

'''Mathematica 6''' by Wolfram Research, is one of a growing number of commercially available scientific/engineering applications. Mathematica does not require multiple processors, but does require significant resources (at least, from the "average" personal computer) - at least 512mb memory. However, on many operating systems Mathematica is able to take advantage of multiple processors, particularly when doing linear algebra equations and dealing with machine-precision real numbers. Wolfram does offer a parallel computing toolkit (http://www.wolfram.com/products/applications/parallel) that allows Mathematica application designers to take advantage of various parallel architectures, ranging from shared memory multiprocessor machines to supercomputers. Wolfram also offers a version of Mathematica tailored to cluster/grid computing, see http://www.wolfram.com/products/gridmathematica/.

There is a trend in HPC towards '''virtualization'''. Virtualization allows application programmers to write applications for virtual machines, not concerning themselves with physical platforms. There are many benefits to running on virtual machines, among them the ability to seamlessly migrate the virtual machines (along with its running applications) off its physical host machine. However, in practice there are many challenges related to virtualization, chief among them the performance limitations they impose (http://www.scientificcomputing.com/ShowPR~PUBCODE~030~ACCT~3000000100~ISSUE~0707~RELTYPE~HPCC~PRODCODE~00000000~PRODLETT~C.html).

== Grand Challenge Problems ==
Some problems are so complex that to solve them would require a significant increase (in some cases by orders of magnitude) in the current computational capabilities of today's computers. These problems are loosely defined as "Grand Challenge Problems." Grand Challenge problems are problems that are solvable, but not in a reasonable period of time on today's computers. Further, a Grand Challenge problem is a problem of some importance, either socially or economically.

'''Biology''' - Human Genome Project (HGP) (http://en.wikipedia.org/wiki/Human_genome_project).
The goal of the HGP is to "understand the genetic makeup of the human species." By some definitions of "complete sequencing" this work was completed in 2003. However, some work remains in that large area of the genome remain unsequenced. Some estimate the genome to be 92% sequenced. The remaining portions , highly repetitive sequences of DNA known as centromeres, are proving difficult with today's technology.

The basic approach to HGP is a classic "divide and conquer". The genome was broken down into smaller pieces, approximately 150,000 base pairs in length, processed separately, then assembled to form chromosones.

'''Physics''' (nuclear technology)

'''Astronomy'''

'''Cognition/Strong AI''' - the idea that computers can become "self aware." (vs. weak AI who's goal is not so grandiose - Turing test)

CSC/ECE 506 Fall 2007/wiki1 2 3K8i

2007-09-05T13:59:33Z

Jfswaffo:

== Trends in Scientific and Engineering Computing ==

Scientific and engineering applications continue to demand the highest performance computers available, a trend established in the early days of supercomputers that continues today in the realm of "High Performance Computing" (HPC). Much work has been done in the areas of computational modeling and simulation. By using modeling, scientists are able to analyze hypothetical designs, rather than relying on empirical evidence, which is often difficult or impossible to come by. Higher performance computers afford the resources to build richer, more complicated models that allow scientists to study more difficult problems. As problems are solved, new, more complex problems arise to take their place. Many Grand Challenge Problems "on the radar" today were not feasible on the supercomputers of a just decade ago. Generally, each successive generation of Grand Challenge problems require more memory and faster processing capabilities. The architectures used to deliver those memory and processing speed requirements are changing, and along with them the algorithms and techniques used to make efficient use of them.

Before looking at some of today's most challenging computational problems, it may be instructive to look at the trends in HPC over the last decade or so.

== Hardware Trends ==
According the the U.S. Army Research Laboratory (http://www.arl.army.mil/www/default.cfm?Action=20&Page=272), there have been five generations of architectures in the realm of scientific computing. They are serial processors (1947-1986), vector processors (1986-2002), shared memory (1993-present), distributed memory (2000-present), and commodity clusters (2001-present).

Indeed, the trend in recent years in multiprocessing has been away from vector architectures and towards low cost, multi-threaded single address spaced systems. (http://www.nus.edu.sg/comcen/svu/publications/SVULink/vol_1_iss_1/hpc-trends.html) Multi-core processors are becoming more and more mainstream. Today, many new desktop systems contain dual cores, with some quad cores being sold. Tony Hey (http://en.wikipedia.org/wiki/Tony_Hey), a leading researcher in parallel computing, has predicted that by 2015, a single socket will contain hundreds of cores. (http://www.accessmylibrary.com/coms2/summary_0286-30177016_ITM)

There have also been strong trends towards cluster and grid computing, which seek to take advantage of multiple, low cost (commodity) computer systems and treat them as a logical entity. Several categories of clusters exists, ranging from high performance computers linked together via high speed interconnects, to geographically separated systems linked together over the Internet. (http://en.wikipedia.org/wiki/Cluster_computing) Grid computing is a form of the latter, generally composed of multiple "collections" of computers (grid elements) that do not necessarily trust each other.

Putting these together, we see a clear movement towards commodity processors in both the areas of parallel computing (processors in a single computer system) and distributed computing (using multiple computer systems). Perhaps the strongest driving force behind these trends is one of supply and demand, or economies of scale. Specialized hardware is, by definition, in less demand then general purpose hardware, making it much more difficult to recover design and production costs. Hence, there is a strong economic incentive for consumers and manufacturers alike to favor more general purpose solutions.

Despite these trends, the "traditional" supercomputer is alive and well. Today's highest performance machines are capable of performing hundreds of teraflops per second. (A teraflop is 1 x 10^12 FLOPS.) As of June 2007, the world's fastest computer, as measured by the Linpack (http://en.wikipedia.org/wiki/Linpack) benchmark, is IBM's massively parallel Blue Gene/L. IBM has plans to build a 3 petaflop (3 x 10^15 FLOPS) machine by fall 2007, and a 10 petaflop machine in the 2010-2012 timeframe. More information on IBM's Blue Gene and other supercomputers can be found at http://www.top500.org/.

== Software Trends ==
With dramatic increases in hardware performance come more demanding applications, which in turn demand higher performance software. Many scientific applications available today, some even commercially, were not available on general purpose architectures even a few years ago.

'''Mathematica 6''' by Wolfram Research, is one of a growing number of commercially available scientific/engineering applications. Mathematica does not require multiple processors, but does require significant resources (at least, from the "average" personal computer) - at least 512mb memory. However, on many operating systems Mathematica is able to take advantage of multiple processors, particularly when doing linear algebra equations and dealing with machine-precision real numbers. Wolfram does offer a parallel computing toolkit (http://www.wolfram.com/products/applications/parallel) that allows Mathematica application designers to take advantage of various parallel architectures, ranging from shared memory multiprocessor machines to supercomputers. Wolfram also offers a version of Mathematica tailored to cluster/grid computing, see http://www.wolfram.com/products/gridmathematica/.

There is a trend in HPC towards '''virtualization'''. Virtualization allows application programmers to write applications for virtual machines, not concerning themselves with physical platforms. There are many benefits to running on virtual machines, among them the ability to seamlessly migrate the virtual machines (along with its running applications) off its physical host machine. However, in practice there are many challenges related to virtualization, chief among them the performance limitations they impose (http://www.scientificcomputing.com/ShowPR~PUBCODE~030~ACCT~3000000100~ISSUE~0707~RELTYPE~HPCC~PRODCODE~00000000~PRODLETT~C.html).

== Grand Challenge Problems ==
Some problems are so complex that to solve them would require a significant increase (in some cases by orders of magnitude) in the current computational capabilities of today's computers. These problems are loosely defined as "Grand Challenge Problems." Grand Challenge problems are problems that are solvable, but not in a reasonable period of time on today's computers. Further, a Grand Challenge problem is a problem of some importance, either socially or economically.

'''Biology''' - Human Genome Project (HGP) (http://en.wikipedia.org/wiki/Human_genome_project).
The goal of the HGP is to "understand the genetic makeup of the human species." By some definitions of "complete sequencing" this work was completed in 2003. However, some work remains in that large area of the genome remain unsequenced. Some estimate the genome to be 92% sequenced. The remaining portions , highly repetitive sequences of DNA known as centromeres, are proving difficult with today's technology.

The basic approach to HGP is a classic "divide and conquer". The genome was broken down into smaller pieces, approximately 150,000 base pairs in length, processed separately, then assembled to form chromosones.

'''Physics''' (nuclear technology)

'''Astronomy'''

'''Cognition/Strong AI''' - the idea that computers can become "self aware." (vs. weak AI who's goal is not so grandiose - Turing test)

'''Game playing''' - chess, checkers (Jonathon Schaefer)

CSC/ECE 506 Fall 2007/wiki1 2 3K8i

2007-09-05T13:58:58Z

Jfswaffo:

== Trends in Scientific and Engineering Computing ==

Scientific and engineering applications continue to demand the highest performance computers available, a trend established in the early days of supercomputers that continues today in the realm of "High Performance Computing" (HPC). Much work has been done in the areas of computational modeling and simulation. By using modeling, scientists are able to analyze hypothetical designs, rather than relying on empirical evidence, which is often difficult or impossible to come by. Higher performance computers afford the resources to build richer, more complicated models that allow scientists to study more difficult problems. As problems are solved, new, more complex problems arise to take their place. Many Grand Challenge Problems "on the radar" today were not feasible on the supercomputers of a just decade ago. Generally, each successive generation of Grand Challenge problems require more memory and faster processing capabilities. The architectures used to deliver those memory and processing speed requirements are changing, and along with them the algorithms and techniques used to make efficient use of them.

Before looking at some of today's most challenging computational problems, it may be instructive to look at the trends in HPC over the last decade or so.

== Hardware Trends ==
According the the U.S. Army Research Laboratory (http://www.arl.army.mil/www/default.cfm?Action=20&Page=272), there have been five generations of architectures in the realm of scientific computing. They are serial processors (1947-1986), vector processors (1986-2002), shared memory (1993-present), distributed memory (2000-present), and commodity clusters (2001-present).

Indeed, the trend in recent years in multiprocessing has been away from vector architectures and towards low cost, multi-threaded single address spaced systems. (http://www.nus.edu.sg/comcen/svu/publications/SVULink/vol_1_iss_1/hpc-trends.html) Multi-core processors are becoming more and more mainstream. Today, many new desktop systems contain dual cores, with some quad cores being sold. Tony Hey (http://en.wikipedia.org/wiki/Tony_Hey), a leading researcher in parallel computing, has predicted that by 2015, a single socket will contain hundreds of cores. (http://www.accessmylibrary.com/coms2/summary_0286-30177016_ITM)

There have also been strong trends towards cluster and grid computing, which seek to take advantage of multiple, low cost (commodity) computer systems and treat them as a logical entity. Several categories of clusters exists, ranging from high performance computers linked together via high speed interconnects, to geographically separated systems linked together over the Internet. (http://en.wikipedia.org/wiki/Cluster_computing) Grid computing is a form of the latter, generally composed of multiple "collections" of computers (grid elements) that do not necessarily trust each other.

Putting these together, we see a clear movement towards commodity processors in both the areas of parallel computing (processors in a single computer system) and distributed computing (using multiple computer systems). Perhaps the strongest driving force behind these trends is one of supply and demand, or economies of scale. Specialized hardware is, by definition, in less demand then general purpose hardware, making it much more difficult to recover design and production costs. Hence, there is a strong economic incentive for consumers and manufacturers alike to favor more general purpose solutions.

Despite these trends, the "traditional" supercomputer is alive and well. Today's highest performance machines are capable of performing hundreds of teraflops per second. (A teraflop is 1 x 10^12 FLOPS.) As of June 2007, the world's fastest computer, as measured by the Linpack (http://en.wikipedia.org/wiki/Linpack) benchmark, is IBM's massively parallel Blue Gene/L. IBM has plans to build a 3 petaflop (3 x 10^15 FLOPS) machine by fall 2007, and a 10 petaflop machine in the 2010-2012 timeframe. More information on IBM's Blue Gene and other supercomputers can be found at http://www.top500.org/.

== Software Trends ==
With dramatic increases in hardware performance come more demanding applications, which in turn demand higher performance software. Many scientific applications available today, some even commercially, were not available on general purpose architectures even a few years ago.

'''Mathematica 6''' by Wolfram Research, is one of a growing number of commercially available scientific/engineering applications. Mathematica does not require multiple processors, but does require significant resources (at least, from the "average" personal computer) - at least 512mb memory. However, on many operating systems Mathematica is able to take advantage of multiple processors, particularly when doing linear algebra equations and dealing with machine-precision real numbers. Wolfram does offer a parallel computing toolkit (http://www.wolfram.com/products/applications/parallel) that allows Mathematica application designers to take advantage of various parallel architectures, ranging from shared memory multiprocessor machines to supercomputers. Wolfram also offers a version of Mathematica tailored to cluster/grid computing, see http://www.wolfram.com/products/gridmathematica/.

There is a trend in HPC towards '''virtualization'''. Virtualization allows application programmers to write applications for virtual machines, not concerning themselves with physical platforms. There are many benefits to running on virtual machines, among them the ability to seamlessly migrate the virtual machines (along with its running applications) off its physical host machine. However, in practice there are many challenges related to virtualization, chief among them the performance limitations they impose (http://www.scientificcomputing.com/ShowPR~PUBCODE~030~ACCT~3000000100~ISSUE~0707~RELTYPE~HPCC~PRODCODE~00000000~PRODLETT~C.html).

== Grand Challenge Problems ==
Some problems are so complex that to solve them would require a significant increase (in some cases by orders of magnitude) in the current computational capabilities of today's computers. These problems are loosely defined as "Grand Challenge Problems." Grand Challenge problems are problems that are solvable, but not in a reasonable period of time on today's computers. Further, a Grand Challenge problem is a problem of some importance, either socially or economically.

'''Biology''' - Human Genome Project (HGP) (http://en.wikipedia.org/wiki/Human_genome_project). The goal of the HGP is to "understand the genetic makeup of the human species." By some definitions of "complete sequencing" this work was completed in 2003. However, some work remains in that large area of the genome remain unsequenced. Some estimate the genome to be 92% sequenced. The remaining portions , highly repetitive sequences of DNA known as centromeres, are proving difficult with today's technology.

The basic approach to HGP is a classic "divide and conquer". The genome was broken down into smaller pieces, approximately 150,000 base pairs in length, processed separately, then assembled to form chromosones.

'''Physics''' (nuclear technology)

'''Astronomy'''

'''Cognition/Strong AI''' - the idea that computers can become "self aware." (vs. weak AI who's goal is not so grandiose - Turing test)

'''Game playing''' - chess, checkers (Jonathon Schaefer)

Linpack benchmark

----

Links:
http://en.wikipedia.org/wiki/High_Performance_Computing

http://www.top500.org/

http://en.wikipedia.org/wiki/Grand_Challenge_problem

http://en.wikipedia.org/wiki/Grand_Challenge

CSC/ECE 506 Fall 2007/wiki1 2 3K8i

2007-09-05T13:38:41Z

Jfswaffo:

== Trends in Scientific and Engineering Computing ==

Scientific and engineering applications continue to demand the highest performance computers available, a trend established in the early days of supercomputers that continues today in the realm of "High Performance Computing" (HPC). Much work has been done in the areas of computational modeling and simulation. By using modeling, scientists are able to analyze hypothetical designs, rather than relying on empirical evidence, which is often difficult or impossible to come by. Higher performance computers afford the resources to build richer, more complicated models that allow scientists to study more difficult problems. As problems are solved, new, more complex problems arise to take their place. Many Grand Challenge Problems "on the radar" today were not feasible on the supercomputers of a just decade ago. Generally, each successive generation of Grand Challenge problems require more memory and faster processing capabilities. The architectures used to deliver those memory and processing speed requirements are changing, and along with them the algorithms and techniques used to make efficient use of them.

Before looking at some of today's most challenging computational problems, it may be instructive to look at the trends in HPC over the last decade or so.

== Hardware Trends ==
According the the U.S. Army Research Laboratory (http://www.arl.army.mil/www/default.cfm?Action=20&Page=272), there have been five generations of architectures in the realm of scientific computing. They are serial processors (1947-1986), vector processors (1986-2002), shared memory (1993-present), distributed memory (2000-present), and commodity clusters (2001-present).

Indeed, the trend in recent years in multiprocessing has been away from vector architectures and towards low cost, multi-threaded single address spaced systems. (http://www.nus.edu.sg/comcen/svu/publications/SVULink/vol_1_iss_1/hpc-trends.html) Multi-core processors are becoming more and more mainstream. Today, many new desktop systems contain dual cores, with some quad cores being sold. Tony Hey (http://en.wikipedia.org/wiki/Tony_Hey), a leading researcher in parallel computing, has predicted that by 2015, a single socket will contain hundreds of cores. (http://www.accessmylibrary.com/coms2/summary_0286-30177016_ITM)

There have also been strong trends towards cluster and grid computing, which seek to take advantage of multiple, low cost (commodity) computer systems and treat them as a logical entity. Several categories of clusters exists, ranging from high performance computers linked together via high speed interconnects, to geographically separated systems linked together over the Internet. (http://en.wikipedia.org/wiki/Cluster_computing) Grid computing is a form of the latter, generally composed of multiple "collections" of computers (grid elements) that do not necessarily trust each other.

Putting these together, we see a clear movement towards commodity processors in both the areas of parallel computing (processors in a single computer system) and distributed computing (using multiple computer systems). Perhaps the strongest driving force behind these trends is one of supply and demand, or economies of scale. Specialized hardware is, by definition, in less demand then general purpose hardware, making it much more difficult to recover design and production costs. Hence, there is a strong economic incentive for consumers and manufacturers alike to favor more general purpose solutions.

Despite these trends, the "traditional" supercomputer is alive and well. Today's highest performance machines are capable of performing hundreds of teraflops per second. (A teraflop is 1 x 10^12 FLOPS.) As of June 2007, the world's fastest computer, as measured by the Linpack (http://en.wikipedia.org/wiki/Linpack) benchmark, is IBM's massively parallel Blue Gene/L. IBM has plans to build a 3 petaflop (3 x 10^15 FLOPS) machine by fall 2007, and a 10 petaflop machine in the 2010-2012 timeframe. More information on IBM's Blue Gene and other supercomputers can be found at http://www.top500.org/.

== Software Trends ==
With dramatic increases in hardware performance come more demanding applications, which in turn demand higher performance software. Many scientific applications available today, some even commercially, were not available on general purpose architectures even a few years ago.

'''Mathematica 6''' by Wolfram Research, is one of a growing number of commercially available scientific/engineering applications. Mathematica does not require multiple processors, but does require significant resources (at least, from the "average" personal computer) - at least 512mb memory. However, on many operating systems Mathematica is able to take advantage of multiple processors, particularly when doing linear algebra equations and dealing with machine-precision real numbers. Wolfram does offer a parallel computing toolkit (http://www.wolfram.com/products/applications/parallel) that allows Mathematica application designers to take advantage of various parallel architectures, ranging from shared memory multiprocessor machines to supercomputers. Wolfram also offers a version of Mathematica tailored to cluster/grid computing, see http://www.wolfram.com/products/gridmathematica/.

There is a trend in HPC towards '''virtualization'''. Virtualization allows application programmers to write applications for virtual machines, not concerning themselves with physical platforms. There are many benefits to running on virtual machines, among them the ability to seamlessly migrate the virtual machines (along with its running applications) off its physical host machine. However, in practice there are many challenges related to virtualization, chief among them the performance limitations they impose (http://www.scientificcomputing.com/ShowPR~PUBCODE~030~ACCT~3000000100~ISSUE~0707~RELTYPE~HPCC~PRODCODE~00000000~PRODLETT~C.html).

== Grand Challenge Problems ==
Some problems are so complex that to solve them would require a significant increase (in some cases by orders of magnitude) in the current computational capabilities of today's computers. These problems are loosely defined as "Grand Challenge Problems." Grand Challenge problems are problems that are solvable, but not in a reasonable period of time on today's computers. Further, a Grand Challenge problem is a problem of some importance, either socially or economically.

'''Biology''' - Human Genome Project (http://en.wikipedia.org/wiki/Human_genome_project)
Looks like a "divide and conquer" approach. The genome was broken down into smaller pieces, approximately 150,000 base pairs in length, processed separately, then assembled to form chromosones.

'''Physics''' (nuclear technology)

'''Astronomy'''

'''Cognition/Strong AI''' - the idea that computers can become "self aware." (vs. weak AI who's goal is not so grandiose - Turing test)

'''Game playing''' - chess, checkers (Jonathon Schaefer)

Linpack benchmark

----

Links:
http://en.wikipedia.org/wiki/High_Performance_Computing

http://www.top500.org/

http://en.wikipedia.org/wiki/Grand_Challenge_problem

http://en.wikipedia.org/wiki/Grand_Challenge

CSC/ECE 506 Fall 2007/wiki1 2 3K8i

2007-09-05T13:37:53Z

Jfswaffo:

== Trends in Scientific and Engineering Computing ==

Scientific and engineering applications continue to demand the highest performance computers available, a trend established in the early days of supercomputers that continues today in the realm of "High Performance Computing" (HPC). Much work has been done in the areas of computational modeling and simulation. By using modeling, scientists are able to analyze hypothetical designs, rather than relying on empirical evidence, which is often difficult or impossible to come by. Higher performance computers afford the resources to build richer, more complicated models that allow scientists to study more difficult problems. As problems are solved, new, more complex problems arise to take their place. Many Grand Challenge Problems "on the radar" today were not feasible on the supercomputers of a just decade ago. Generally, each successive generation of Grand Challenge problems require more memory and faster processing capabilities. The architectures used to deliver those memory and processing speed requirements are changing, and along with them the algorithms and techniques used to make efficient use of them.

Before looking at some of today's most challenging computational problems, it may be instructive to look at the trends in HPC over the last decade or so.

== Hardware Trends ==
According the the U.S. Army Research Laboratory (http://www.arl.army.mil/www/default.cfm?Action=20&Page=272), there have been five generations of architectures in the realm of scientific computing. They are serial processors (1947-1986), vector processors (1986-2002), shared memory (1993-present), distributed memory (2000-present), and commodity clusters (2001-present).

Indeed, the trend in recent years in multiprocessing has been away from vector architectures and towards low cost, multi-threaded single address spaced systems. (http://www.nus.edu.sg/comcen/svu/publications/SVULink/vol_1_iss_1/hpc-trends.html) Multi-core processors are becoming more and more mainstream. Today, many new desktop systems contain dual cores, with some quad cores being sold. Tony Hey (http://en.wikipedia.org/wiki/Tony_Hey), a leading researcher in parallel computing, has predicted that by 2015, a single socket will contain hundreds of cores. (http://www.accessmylibrary.com/coms2/summary_0286-30177016_ITM)

There have also been strong trends towards cluster and grid computing, which seek to take advantage of multiple, low cost (commodity) computer systems and treat them as a logical entity. Several categories of clusters exists, ranging from high performance computers linked together via high speed interconnects, to geographically separated systems linked together over the Internet. (http://en.wikipedia.org/wiki/Cluster_computing) Grid computing is a form of the latter, generally composed of multiple "collections" of computers (grid elements) that do not necessarily trust each other.

Putting these together, we see a clear movement towards commodity processors in both the areas of parallel computing (processors in a single computer system) and distributed computing (using multiple computer systems). Perhaps the strongest driving force behind these trends is one of supply and demand, or economies of scale. Specialized hardware is, by definition, in less demand then general purpose hardware, making it much more difficult to recover design and production costs. Hence, there is a strong economic incentive for consumers and manufacturers alike to favor more general purpose solutions.

Despite these trends, the "traditional" supercomputer is alive and well. Today's highest performance machines are capable of performing hundreds of teraflops per second. (A teraflop is 1 x 10^12 FLOPS.) As of June 2007, the world's fastest computer, as measured by the Linpack (http://en.wikipedia.org/wiki/Linpack) benchmark, is IBM's massively parallel Blue Gene/L. IBM has plans to build a 3 petaflop (3 x 10^15 FLOPS) machine by fall 2007, and a 10 petaflop machine in the 2010-2012 timeframe. More information on IBM's Blue Gene and other supercomputers can be found at http://www.top500.org/.

== Software Trends ==
With dramatic increases in hardware performance come more demanding applications, which in turn demand higher performance software. Many scientific applications available today, some even commercially, were not available on general purpose architectures even a few years ago.

'''Mathematica 6''' by Wolfram Research, is one of a growing number of commercially available scientific/engineering applications. Mathematica does not require multiple processors, but does require significant resources (at least, from the "average" personal computer) - at least 512mb memory. However, on many operating systems Mathematica is able to take advantage of multiple processors, particularly when doing linear algebra equations and dealing with machine-precision real numbers. Wolfram does offer a parallel computing toolkit (http://www.wolfram.com/products/applications/parallel) that allows Mathematica application designers to take advantage of various parallel architectures, ranging from shared memory multiprocessor machines to supercomputers. Wolfram also offers a version of Mathematica tailored to cluster/grid computing, see http://www.wolfram.com/products/gridmathematica/.

There is a trend in HPC towards virtualization. Virtualization allows application programmers to write applications for virtual machines, not concerning themselves with physical platforms. There are many benefits to running on virtual machines, among them the ability to seamlessly migrate the virtual machines (along with its running applications) off its physical host machine. However, in practice there are many challenges related to virtualization, chief among them the performance limitations they impose (http://www.scientificcomputing.com/ShowPR~PUBCODE~030~ACCT~3000000100~ISSUE~0707~RELTYPE~HPCC~PRODCODE~00000000~PRODLETT~C.html).

== Grand Challenge Problems ==
Some problems are so complex that to solve them would require a significant increase (in some cases by orders of magnitude) in the current computational capabilities of today's computers. These problems are loosely defined as "Grand Challenge Problems." Grand Challenge problems are problems that are solvable, but not in a reasonable period of time on today's computers. Further, a Grand Challenge problem is a problem of some importance, either socially or economically.

'''Biology''' - Human Genome Project (http://en.wikipedia.org/wiki/Human_genome_project)
Looks like a "divide and conquer" approach. The genome was broken down into smaller pieces, approximately 150,000 base pairs in length, processed separately, then assembled to form chromosones.

'''Physics''' (nuclear technology)

'''Astronomy'''

'''Cognition/Strong AI''' - the idea that computers can become "self aware." (vs. weak AI who's goal is not so grandiose - Turing test)

'''Game playing''' - chess, checkers (Jonathon Schaefer)

Linpack benchmark

----

Links:
http://en.wikipedia.org/wiki/High_Performance_Computing

http://www.top500.org/

http://en.wikipedia.org/wiki/Grand_Challenge_problem

http://en.wikipedia.org/wiki/Grand_Challenge

CSC/ECE 506 Fall 2007/wiki1 2 3K8i

2007-09-05T13:36:19Z

Jfswaffo:

== Trends in Scientific and Engineering Computing ==

Scientific and engineering applications continue to demand the highest performance computers available, a trend established in the early days of supercomputers that continues today in the realm of "High Performance Computing" (HPC). Much work has been done in the areas of computational modeling and simulation. By using modeling, scientists are able to analyze hypothetical designs, rather than relying on empirical evidence, which is often difficult or impossible to come by. Higher performance computers afford the resources to build richer, more complicated models that allow scientists to study more difficult problems. As problems are solved, new, more complex problems arise to take their place. Many Grand Challenge Problems "on the radar" today were not feasible on the supercomputers of a just decade ago. Generally, each successive generation of Grand Challenge problems require more memory and faster processing capabilities. The architectures used to deliver those memory and processing speed requirements are changing, and along with them the algorithms and techniques used to make efficient use of them.

Before looking at some of today's most challenging computational problems, it may be instructive to look at the trends in HPC over the last decade or so.

== Hardware Trends ==
According the the U.S. Army Research Laboratory (http://www.arl.army.mil/www/default.cfm?Action=20&Page=272), there have been five generations of architectures in the realm of scientific computing. They are serial processors (1947-1986), vector processors (1986-2002), shared memory (1993-present), distributed memory (2000-present), and commodity clusters (2001-present).

Indeed, the trend in recent years in multiprocessing has been away from vector architectures and towards low cost, multi-threaded single address spaced systems. (http://www.nus.edu.sg/comcen/svu/publications/SVULink/vol_1_iss_1/hpc-trends.html) Multi-core processors are becoming more and more mainstream. Today, many new desktop systems contain dual cores, with some quad cores being sold. Tony Hey (http://en.wikipedia.org/wiki/Tony_Hey), a leading researcher in parallel computing, has predicted that by 2015, a single socket will contain hundreds of cores. (http://www.accessmylibrary.com/coms2/summary_0286-30177016_ITM)

There have also been strong trends towards cluster and grid computing, which seek to take advantage of multiple, low cost (commodity) computer systems and treat them as a logical entity. Several categories of clusters exists, ranging from high performance computers linked together via high speed interconnects, to geographically separated systems linked together over the Internet. (http://en.wikipedia.org/wiki/Cluster_computing) Grid computing is a form of the latter, generally composed of multiple "collections" of computers (grid elements) that do not necessarily trust each other.

Putting these together, we see a clear movement towards commodity processors in both the areas of parallel computing (processors in a single computer system) and distributed computing (using multiple computer systems). Perhaps the strongest driving force behind these trends is one of supply and demand, or economies of scale. Specialized hardware is, by definition, in less demand then general purpose hardware, making it much more difficult to recover design and production costs. Hence, there is a strong economic incentive for consumers and manufacturers alike to favor more general purpose solutions.

Despite these trends, the "traditional" supercomputer is alive and well. Today's highest performance machines are capable of performing hundreds of teraflops per second. (A teraflop is 1 x 10^12 FLOPS.) As of June 2007, the world's fastest computer, as measured by the Linpack (http://en.wikipedia.org/wiki/Linpack) benchmark, is IBM's massively parallel Blue Gene/L. IBM has plans to build a 3 petaflop (3 x 10^15 FLOPS) machine by fall 2007, and a 10 petaflop machine in the 2010-2012 timeframe. More information on IBM's Blue Gene and other supercomputers can be found at http://www.top500.org/.

== Software Trends ==
With dramatic increases in hardware performance come more demanding applications, which in turn demand higher performance software. Many scientific applications available today, some even commercially, were not available on general purpose architectures even a few years ago.

'''Mathematica 6''' by Wolfram Research, is one of a growing number of commercially available scientific/engineering applications. Mathematica does not require multiple processors, but does require significant resources (at least, from the "average" personal computer) - at least 512mb memory. However, on many operating systems Mathematica is able to take advantage of multiple processors, focusing on linear algebra and machine-precision real numbers. Wolfram does offer a parallel computing toolkit (http://www.wolfram.com/products/applications/parallel) that allows Mathematica application designers to take advantage of various parallel architectures, ranging from shared memory multiprocessor machines to supercomputers. Wolfram also offers a version of Mathematica tailored to cluster/grid computing, see http://www.wolfram.com/products/gridmathematica/.

There is a trend in HPC towards virtualization. Virtualization allows application programmers to write applications for virtual machines, not concerning themselves with physical platforms. There are many benefits to running on virtual machines, among them the ability to seamlessly migrate the virtual machines (along with its running applications) off its physical host machine. However, in practice there are many challenges related to virtualization, chief among them the performance limitations they impose (http://www.scientificcomputing.com/ShowPR~PUBCODE~030~ACCT~3000000100~ISSUE~0707~RELTYPE~HPCC~PRODCODE~00000000~PRODLETT~C.html).

== Grand Challenge Problems ==
Some problems are so complex that to solve them would require a significant increase (in some cases by orders of magnitude) in the current computational capabilities of today's computers. These problems are loosely defined as "Grand Challenge Problems." Grand Challenge problems are problems that are solvable, but not in a reasonable period of time on today's computers. Further, a Grand Challenge problem is a problem of some importance, either socially or economically.

'''Biology''' - Human Genome Project (http://en.wikipedia.org/wiki/Human_genome_project)
Looks like a "divide and conquer" approach. The genome was broken down into smaller pieces, approximately 150,000 base pairs in length, processed separately, then assembled to form chromosones.

'''Physics''' (nuclear technology)

'''Astronomy'''

'''Cognition/Strong AI''' - the idea that computers can become "self aware." (vs. weak AI who's goal is not so grandiose - Turing test)

'''Game playing''' - chess, checkers (Jonathon Schaefer)

Linpack benchmark

----

Links:
http://en.wikipedia.org/wiki/High_Performance_Computing

http://www.top500.org/

http://en.wikipedia.org/wiki/Grand_Challenge_problem

http://en.wikipedia.org/wiki/Grand_Challenge

CSC/ECE 506 Fall 2007/wiki1 2 3K8i

2007-09-05T13:34:17Z

Jfswaffo:

== Trends in Scientific and Engineering Computing ==

Scientific and engineering applications continue to demand the highest performance computers available, a trend established in the early days of supercomputers that continues today in the realm of "High Performance Computing" (HPC). Much work has been done in the areas of computational modeling and simulation. By using modeling, scientists are able to analyze hypothetical designs, rather than relying on empirical evidence, which is often difficult or impossible to come by. Higher performance computers afford the resources to build richer, more complicated models that allow scientists to study more difficult problems. As problems are solved, new, more complex problems arise to take their place. Many Grand Challenge Problems "on the radar" today were not feasible on the supercomputers of a just decade ago. Generally, each successive generation of Grand Challenge problems require more memory and faster processing capabilities. The architectures used to deliver those memory and processing speed requirements are changing, and along with them the algorithms and techniques used to make efficient use of them.

Before looking at some of today's most challenging computational problems, it may be instructive to look at the trends in HPC over the last decade or so.

== Hardware Trends ==
According the the U.S. Army Research Laboratory (http://www.arl.army.mil/www/default.cfm?Action=20&Page=272), there have been five generations of architectures in the realm of scientific computing. They are serial processors (1947-1986), vector processors (1986-2002), shared memory (1993-present), distributed memory (2000-present), and commodity clusters (2001-present).

Indeed, the trend in recent years in multiprocessing has been away from vector architectures and towards low cost, multi-threaded single address spaced systems. (http://www.nus.edu.sg/comcen/svu/publications/SVULink/vol_1_iss_1/hpc-trends.html) Multi-core processors are becoming more and more mainstream. Today, many new desktop systems contain dual cores, with some quad cores being sold. Tony Hey (http://en.wikipedia.org/wiki/Tony_Hey), a leading researcher in parallel computing, has predicted that by 2015, a single socket will contain hundreds of cores. (http://www.accessmylibrary.com/coms2/summary_0286-30177016_ITM)

There have also been strong trends towards cluster and grid computing, which seek to take advantage of multiple, low cost (commodity) computer systems and treat them as a logical entity. Several categories of clusters exists, ranging from high performance computers linked together via high speed interconnects, to geographically separated systems linked together over the Internet. (http://en.wikipedia.org/wiki/Cluster_computing) Grid computing is a form of the latter, generally composed of multiple "collections" of computers (grid elements) that do not necessarily trust each other.

Putting these together, we see a clear movement towards commodity processors in both the areas of parallel computing (processors in a single computer system) and distributed computing (using multiple computer systems). Perhaps the strongest driving force behind these trends is one of supply and demand, or economies of scale. Specialized hardware is, by definition, in less demand then general purpose hardware, making it much more difficult to recover design and production costs. Hence, there is a strong economic incentive for consumers and manufacturers alike to favor more general purpose solutions.

Despite these trends, the "traditional" supercomputer is alive and well. Today's highest performance machines are capable of performing hundreds of teraflops per second. (A teraflop is 1 x 10^12 FLOPS.) As of June 2007, the world's fastest computer, as measured by the Linpack (http://en.wikipedia.org/wiki/Linpack) benchmark, is IBM's massively parallel Blue Gene/L. IBM has plans to build a 3 petaflop (3 x 10^15 FLOPS) machine by fall 2007, and a 10 petaflop machine in the 2010-2012 timeframe. More information on IBM's Blue Gene and other supercomputers can be found at http://www.top500.org/.

== Software Trends ==
With dramatic increases in hardware performance come more demanding applications, which in turn demand higher performance software. Many scientific applications available today, some even commercially, were not available on general purpose architectures even a few years ago.

'''Mathematica 6''' by Wolfram Research, is one of a growing number of commercially available scientific/engineering applications. Mathematica does not require parallel processors, but does require significant resources (at least, from the "average" personal computer) - at least 512mb memory. However, on many operating systems Mathematica is able to take advantage of multiple processors, focusing on linear algebra and machine-precision real numbers. Wolfram does offer a parallel computing toolkit (http://www.wolfram.com/products/applications/parallel) that allows Mathematica application designers to take advantage of various parallel architectures, ranging from shared memory multiprocessor machines to supercomputers. Wolfram also offers a version of Mathematica tailored to cluster/grid computing, see http://www.wolfram.com/products/gridmathematica/.

There is a trend in HPC towards virtualization. Virtualization allows application programmers to write applications for virtual machines, not concerning themselves with physical platforms. There are many benefits to running on virtual machines, among them the ability to seamlessly migrate the virtual machines (along with its running applications) off its physical host machine. However, in practice there are many challenges related to virtualization, chief among them the performance limitations they impose (http://www.scientificcomputing.com/ShowPR~PUBCODE~030~ACCT~3000000100~ISSUE~0707~RELTYPE~HPCC~PRODCODE~00000000~PRODLETT~C.html).

== Grand Challenge Problems ==
Some problems are so complex that to solve them would require a significant increase (in some cases by orders of magnitude) in the current computational capabilities of today's computers. These problems are loosely defined as "Grand Challenge Problems." Grand Challenge problems are problems that are solvable, but not in a reasonable period of time on today's computers. Further, a Grand Challenge problem is a problem of some importance, either socially or economically.

'''Biology''' - Human Genome Project (http://en.wikipedia.org/wiki/Human_genome_project)
Looks like a "divide and conquer" approach. The genome was broken down into smaller pieces, approximately 150,000 base pairs in length, processed separately, then assembled to form chromosones.

'''Physics''' (nuclear technology)

'''Astronomy'''

'''Cognition/Strong AI''' - the idea that computers can become "self aware." (vs. weak AI who's goal is not so grandiose - Turing test)

'''Game playing''' - chess, checkers (Jonathon Schaefer)

Linpack benchmark

----

Links:
http://en.wikipedia.org/wiki/High_Performance_Computing

http://www.top500.org/

http://en.wikipedia.org/wiki/Grand_Challenge_problem

http://en.wikipedia.org/wiki/Grand_Challenge

CSC/ECE 506 Fall 2007/wiki1 2 3K8i

2007-09-05T13:33:29Z

Jfswaffo:

== Trends in Scientific and Engineering Computing ==

Scientific and engineering applications continue to demand the highest performance computers available, a trend established in the early days of supercomputers that continues today in the realm of "High Performance Computing" (HPC). Much work has been done in the areas of computational modeling and simulation. By using modeling, scientists are able to analyze hypothetical designs, rather than relying on empirical evidence, which is often difficult or impossible to come by. Higher performance computers afford the resources to build richer, more complicated models that allow scientists to study more difficult problems. As problems are solved, new, more complex problems arise to take their place. Many Grand Challenge Problems "on the radar" today were not feasible on the supercomputers of a just decade ago. Generally, each successive generation of Grand Challenge problems require more memory and faster processing capabilities. The architectures used to deliver those memory and processing speed requirements are changing, and along with them the algorithms and techniques used to make efficient use of them.

Before looking at some of today's most challenging computational problems, it may be instructive to look at the trends in HPC over the last decade or so.

== Hardware Trends ==
According the the U.S. Army Research Laboratory (http://www.arl.army.mil/www/default.cfm?Action=20&Page=272), there have been five generations of architectures in the realm of scientific computing. They are serial processors (1947-1986), vector processors (1986-2002), shared memory (1993-present), distributed memory (2000-present), and commodity clusters (2001-present).

Indeed, the trend in recent years in multiprocessing has been away from vector architectures and towards low cost, multi-threaded single address spaced systems. (http://www.nus.edu.sg/comcen/svu/publications/SVULink/vol_1_iss_1/hpc-trends.html) Multi-core processors are becoming more and more mainstream. Today, many new desktop systems contain dual cores, with some quad cores being sold. Tony Hey (http://en.wikipedia.org/wiki/Tony_Hey), a leading researcher in parallel computing, has predicted that by 2015, a single socket will contain hundreds of cores. (http://www.accessmylibrary.com/coms2/summary_0286-30177016_ITM)

There have also been strong trends towards cluster and grid computing, which seek to take advantage of multiple, low cost (commodity) computer systems and treat them as a logical entity. Several categories of clusters exists, ranging from high performance computers linked together via high speed interconnects, to geographically separated systems linked together over the Internet. (http://en.wikipedia.org/wiki/Cluster_computing) Grid computing is a form of the latter, generally composed of multiple "collections" of computers (grid elements) that do not necessarily trust each other.

Putting these together, we see a clear movement towards commodity processors in both the areas of parallel computing (processors in a single computer system) and distributed computing (using multiple computer systems). Perhaps the strongest driving force behind these trends is one of supply and demand, or economies of scale. Specialized hardware is, by definition, in less demand then general purpose hardware, making it much more difficult to recover design and production costs. Hence, there is a strong economic incentive for consumers and manufacturers alike to favor more general purpose solutions.

Despite these trends, the "traditional" supercomputer is alive and well. Today's highest performance machines are capable of performing hundreds of teraflops per second. (A teraflop is 1 x 10^12 FLOPS.) As of June 2007, the world's fastest computer, as measured by the Linpack (http://en.wikipedia.org/wiki/Linpack) benchmark, is IBM's massively parallel Blue Gene/L. IBM has plans to build a 3 petaflop (3 x 10^15 FLOPS) machine by fall 2007, and a 10 petaflop machine in the 2010-2012 timeframe. More information on IBM's Blue Gene and other supercomputers can be found at http://www.top500.org/.

== Software Trends ==
With dramatic increases in hardware performance come more demanding applications, which in turn demand higher performance software. Many scientific applications available today, some even commercially, were not available on general purpose architectures even a few years ago.

'''Mathematica 6''' by Wolfram Research, is one of a growing number of commercially available scientific/engineering applications. Mathematica does not require parallel processors, but does require significant resources (at least, from the "average" personal computer) - at least 512mb memory. However, on many operating systems Mathematica is able to take advantage of multiple processors, focusing on linear algebra and machine-precision real numbers. Wolfram does offer a parallel computing toolkit (http://www.wolfram.com/products/applications/parallel) that allows Mathematica application designers to take advantage of various parallel architectures, ranging from shared memory multiprocessor machines to supercomputers. Wolfram also offers a version of Mathematica tailored to cluster/grid computing, see http://www.wolfram.com/products/gridmathematica/.

There is a trend in HPC towards virtualization. Virtualization allows application programmers to write applications for virtual machines, not concerning themselves with physical platforms. There are many benefits to running on virtual machines, among them the ability to seamlessly migrate the virtual machines (along with its running applications) off its physical host machine. However, in practice there are many challenges related to virtualization, chief among them the performance limitations they impose (http://www.scientificcomputing.com/ShowPR~PUBCODE~030~ACCT~3000000100~ISSUE~0707~RELTYPE~HPCC~PRODCODE~00000000~PRODLETT~C.html).

== Grand Challenge Problems ==
Some problems are so complex that to solve them would require a significant increase (in some cases by orders of magnitude) in the current computational capabilities of today's computers. These problems are loosely defined as "Grand Challenge Problems." Grand Challenge problems are problems that are solvable, but not in a reasonable period of time on today's computers. Further, a grand challenge problem is a problem of some importance, either socially or economically.

'''Biology''' - Human Genome Project (http://en.wikipedia.org/wiki/Human_genome_project)
Looks like a "divide and conquer" approach. The genome was broken down into smaller pieces, approximately 150,000 base pairs in length, processed separately, then assembled to form chromosones.

'''Physics''' (nuclear technology)

'''Astronomy'''

'''Cognition/Strong AI''' - the idea that computers can become "self aware." (vs. weak AI who's goal is not so grandiose - Turing test)

'''Game playing''' - chess, checkers (Jonathon Schaefer)

Linpack benchmark

----

Links:
http://en.wikipedia.org/wiki/High_Performance_Computing

http://www.top500.org/

http://en.wikipedia.org/wiki/Grand_Challenge_problem

http://en.wikipedia.org/wiki/Grand_Challenge

CSC/ECE 506 Fall 2007/wiki1 2 3K8i

2007-09-05T13:32:57Z

Jfswaffo:

== Trends in Scientific and Engineering Computing ==

Scientific and engineering applications continue to demand the highest performance computers available, a trend established in the early days of supercomputers that continues today in the realm of "High Performance Computing" (HPC). Much work has been done in the areas of computational modeling and simulation. By using modeling, scientists are able to analyze hypothetical designs, rather than relying on empirical evidence, which is often difficult or impossible to come by. Higher performance computers afford the resources to build richer, more complicated models that allow scientist to study more difficult problems. As problems are solved, new, more complex problems arise to take their place. Many Grand Challenge Problems "on the radar" today were not feasible on the supercomputers of a just decade ago. Generally, each successive generation of Grand Challenge problems require more memory and faster processing capabilities. The architectures used to deliver those memory and processing speed requirements are changing, and along with them the algorithms and techniques used to make efficient use of them.

Before looking at some of today's most challenging computational problems, it may be instructive to look at the trends in HPC over the last decade or so.

== Hardware Trends ==
According the the U.S. Army Research Laboratory (http://www.arl.army.mil/www/default.cfm?Action=20&Page=272), there have been five generations of architectures in the realm of scientific computing. They are serial processors (1947-1986), vector processors (1986-2002), shared memory (1993-present), distributed memory (2000-present), and commodity clusters (2001-present).

Indeed, the trend in recent years in multiprocessing has been away from vector architectures and towards low cost, multi-threaded single address spaced systems. (http://www.nus.edu.sg/comcen/svu/publications/SVULink/vol_1_iss_1/hpc-trends.html) Multi-core processors are becoming more and more mainstream. Today, many new desktop systems contain dual cores, with some quad cores being sold. Tony Hey (http://en.wikipedia.org/wiki/Tony_Hey), a leading researcher in parallel computing, has predicted that by 2015, a single socket will contain hundreds of cores. (http://www.accessmylibrary.com/coms2/summary_0286-30177016_ITM)

There have also been strong trends towards cluster and grid computing, which seek to take advantage of multiple, low cost (commodity) computer systems and treat them as a logical entity. Several categories of clusters exists, ranging from high performance computers linked together via high speed interconnects, to geographically separated systems linked together over the Internet. (http://en.wikipedia.org/wiki/Cluster_computing) Grid computing is a form of the latter, generally composed of multiple "collections" of computers (grid elements) that do not necessarily trust each other.

Putting these together, we see a clear movement towards commodity processors in both the areas of parallel computing (processors in a single computer system) and distributed computing (using multiple computer systems). Perhaps the strongest driving force behind these trends is one of supply and demand, or economies of scale. Specialized hardware is, by definition, in less demand then general purpose hardware, making it much more difficult to recover design and production costs. Hence, there is a strong economic incentive for consumers and manufacturers alike to favor more general purpose solutions.

Despite these trends, the "traditional" supercomputer is alive and well. Today's highest performance machines are capable of performing hundreds of teraflops per second. (A teraflop is 1 x 10^12 FLOPS.) As of June 2007, the world's fastest computer, as measured by the Linpack (http://en.wikipedia.org/wiki/Linpack) benchmark, is IBM's massively parallel Blue Gene/L. IBM has plans to build a 3 petaflop (3 x 10^15 FLOPS) machine by fall 2007, and a 10 petaflop machine in the 2010-2012 timeframe. More information on IBM's Blue Gene and other supercomputers can be found at http://www.top500.org/.

== Software Trends ==
With dramatic increases in hardware performance come more demanding applications, which in turn demand higher performance software. Many scientific applications available today, some even commercially, were not available on general purpose architectures even a few years ago.

'''Mathematica 6''' by Wolfram Research, is one of a growing number of commercially available scientific/engineering applications. Mathematica does not require parallel processors, but does require significant resources (at least, from the "average" personal computer) - at least 512mb memory. However, on many operating systems Mathematica is able to take advantage of multiple processors, focusing on linear algebra and machine-precision real numbers. Wolfram does offer a parallel computing toolkit (http://www.wolfram.com/products/applications/parallel) that allows Mathematica application designers to take advantage of various parallel architectures, ranging from shared memory multiprocessor machines to supercomputers. Wolfram also offers a version of Mathematica tailored to cluster/grid computing, see http://www.wolfram.com/products/gridmathematica/.

There is a trend in HPC towards virtualization. Virtualization allows application programmers to write applications for virtual machines, not concerning themselves with physical platforms. There are many benefits to running on virtual machines, among them the ability to seamlessly migrate the virtual machines (along with its running applications) off its physical host machine. However, in practice there are many challenges related to virtualization, chief among them the performance limitations they impose (http://www.scientificcomputing.com/ShowPR~PUBCODE~030~ACCT~3000000100~ISSUE~0707~RELTYPE~HPCC~PRODCODE~00000000~PRODLETT~C.html).

== Grand Challenge Problems ==
Some problems are so complex that to solve them would require a significant increase (in some cases by orders of magnitude) in the current computational capabilities of today's computers. These problems are loosely defined as "Grand Challenge Problems." Grand Challenge problems are problems that are solvable, but not in a reasonable period of time on today's computers. Further, a grand challenge problem is a problem of some importance, either socially or economically.

'''Biology''' - Human Genome Project (http://en.wikipedia.org/wiki/Human_genome_project)
Looks like a "divide and conquer" approach. The genome was broken down into smaller pieces, approximately 150,000 base pairs in length, processed separately, then assembled to form chromosones.

'''Physics''' (nuclear technology)

'''Astronomy'''

'''Cognition/Strong AI''' - the idea that computers can become "self aware." (vs. weak AI who's goal is not so grandiose - Turing test)

'''Game playing''' - chess, checkers (Jonathon Schaefer)

Linpack benchmark

----

Links:
http://en.wikipedia.org/wiki/High_Performance_Computing

http://www.top500.org/

http://en.wikipedia.org/wiki/Grand_Challenge_problem

http://en.wikipedia.org/wiki/Grand_Challenge

CSC/ECE 506 Fall 2007/wiki1 2 3K8i

2007-09-05T13:25:44Z

Jfswaffo:

== Trends in Scientific and Engineering Computing ==

Scientific and engineering applications continue to demand the highest performance computers available, a trend established in the early days of supercomputers that continues today in the realm of "High Performance Computing" (HPC). As problems are solved, new, more complex problems arise to take their place. Many Grand Challenge Problems "on the radar" today were not feasible on the supercomputers of a just decade ago. Generally, each successive generation of Grand Challenge problems require more memory and faster processing capabilities. The architectures used to deliver those memory and processing speed requirements are changing, and along with them the algorithms and techniques used to make efficient use of them.

Before looking at some of today's most challenging computational problems, it may be instructive to look at the trends in HPC over the last decade or so.

== Hardware Trends ==
According the the U.S. Army Research Laboratory (http://www.arl.army.mil/www/default.cfm?Action=20&Page=272), there have been five generations of architectures in the realm of scientific computing. They are serial processors (1947-1986), vector processors (1986-2002), shared memory (1993-present), distributed memory (2000-present), and commodity clusters (2001-present).

Indeed, the trend in recent years in multiprocessing has been away from vector architectures and towards low cost, multi-threaded single address spaced systems. (http://www.nus.edu.sg/comcen/svu/publications/SVULink/vol_1_iss_1/hpc-trends.html) Multi-core processors are becoming more and more mainstream. Today, many new desktop systems contain dual cores, with some quad cores being sold. Tony Hey (http://en.wikipedia.org/wiki/Tony_Hey), a leading researcher in parallel computing, has predicted that by 2015, a single socket will contain hundreds of cores. (http://www.accessmylibrary.com/coms2/summary_0286-30177016_ITM)

There have also been strong trends towards cluster and grid computing, which seek to take advantage of multiple, low cost (commodity) computer systems and treat them as a logical entity. Several categories of clusters exists, ranging from high performance computers linked together via high speed interconnects, to geographically separated systems linked together over the Internet. (http://en.wikipedia.org/wiki/Cluster_computing) Grid computing is a form of the latter, generally composed of multiple "collections" of computers (grid elements) that do not necessarily trust each other.

Putting these together, we see a clear movement towards commodity processors in both the areas of parallel computing (processors in a single computer system) and distributed computing (using multiple computer systems). Perhaps the strongest driving force behind these trends is one of supply and demand, or economies of scale. Specialized hardware is, by definition, in less demand then general purpose hardware, making it much more difficult to recover design and production costs. Hence, there is a strong economic incentive for consumers and manufacturers alike to favor more general purpose solutions.

Despite these trends, the "traditional" supercomputer is alive and well. Today's highest performance machines are capable of performing hundreds of teraflops per second. (A teraflop is 1 x 10^12 FLOPS.) As of June 2007, the world's fastest computer, as measured by the Linpack (http://en.wikipedia.org/wiki/Linpack) benchmark, is IBM's massively parallel Blue Gene/L. IBM has plans to build a 3 petaflop (3 x 10^15 FLOPS) machine by fall 2007, and a 10 petaflop machine in the 2010-2012 timeframe. More information on IBM's Blue Gene and other supercomputers can be found at http://www.top500.org/.

== Software Trends ==
With dramatic increases in hardware performance come more demanding applications, which in turn demand higher performance software. Many scientific applications available today, some even commercially, were not available on general purpose architectures even a few years ago.

'''Mathematica 6''' by Wolfram Research, is one of a growing number of commercially available scientific/engineering applications. Mathematica does not require parallel processors, but does require significant resources (at least, from the "average" personal computer) - at least 512mb memory. However, on many operating systems Mathematica is able to take advantage of multiple processors, focusing on linear algebra and machine-precision real numbers. Wolfram does offer a parallel computing toolkit (http://www.wolfram.com/products/applications/parallel) that allows Mathematica application designers to take advantage of various parallel architectures, ranging from shared memory multiprocessor machines to supercomputers. Wolfram also offers a version of Mathematica tailored to cluster/grid computing, see http://www.wolfram.com/products/gridmathematica/.

There is a trend in HPC towards virtualization. Virtualization allows application programmers to write applications for virtual machines, not concerning themselves with physical platforms. There are many benefits to running on virtual machines, among them the ability to seamlessly migrate the virtual machines (along with its running applications) off its physical host machine. However, in practice there are many challenges related to virtualization, chief among them the performance limitations they impose (http://www.scientificcomputing.com/ShowPR~PUBCODE~030~ACCT~3000000100~ISSUE~0707~RELTYPE~HPCC~PRODCODE~00000000~PRODLETT~C.html).

== Grand Challenge Problems ==
Some problems are so complex that to solve them would require a significant increase (in some cases by orders of magnitude) in the current computational capabilities of today's computers. These problems are loosely defined as "Grand Challenge Problems." Grand Challenge problems are problems that are solvable, but not in a reasonable period of time on today's computers. Further, a grand challenge problem is a problem of some importance, either socially or economically.

Computational modeling/simulation: why, benefits. in-depth analysis can be performed cheaply on hypothetical designs.
There is a direct correlation between computational performance and the problems that can be studied through simulation.

'''Biology''' - Human Genome Project (http://en.wikipedia.org/wiki/Human_genome_project)
Looks like a "divide and conquer" approach. The genome was broken down into smaller pieces, approximately 150,000 base pairs in length, processed separately, then assembled to form chromosones.

'''Physics''' (nuclear technology)

'''Astronomy'''

'''Cognition/Strong AI''' - the idea that computers can become "self aware." (vs. weak AI who's goal is not so grandiose - Turing test)

'''Game playing''' - chess, checkers (Jonathon Schaefer)

Linpack benchmark

----

Links:
http://en.wikipedia.org/wiki/High_Performance_Computing

http://www.top500.org/

http://en.wikipedia.org/wiki/Grand_Challenge_problem

http://en.wikipedia.org/wiki/Grand_Challenge

CSC/ECE 506 Fall 2007/wiki1 2 3K8i

2007-09-04T00:33:49Z

Jfswaffo:

== Trends in Scientific and Engineering Computing ==

Scientific and engineering applications continue to demand the highest performance computers available, a trend established in the early days of supercomputers that continues today in the realm of "High Performance Computing" (HPC). As problems are solved, new, more complex problems arise to take their place. Many Grand Challenge Problems "on the radar" today were not feasible on the supercomputers of a just decade ago. Generally, each successive generation of Grand Challenge problems require more memory and faster processing capabilities. The architectures used to deliver those memory and processing speed requirements are changing, and along with them the algorithms and techniques used to make efficient use of them.

Before looking at some of today's most challenging computational problems, it may be instructive to look at the trends in HPC over the last decade or so.

== Hardware Trends ==
According the the U.S. Army Research Laboratory (http://www.arl.army.mil/www/default.cfm?Action=20&Page=272), there have been five generations of architectures in the realm of scientific computing. They are serial processors (1947-1986), vector processors (1986-2002), shared memory (1993-present), distributed memory (2000-present), and commodity clusters (2001-present).

Indeed, the trend in recent years in multiprocessing has been away from vector architectures and towards low cost, multi-threaded single address spaced systems. (http://www.nus.edu.sg/comcen/svu/publications/SVULink/vol_1_iss_1/hpc-trends.html) Multi-core processors are becoming more and more mainstream. Today, many new desktop systems contain dual cores, with some quad cores being sold. Tony Hey (http://en.wikipedia.org/wiki/Tony_Hey), a leading researcher in parallel computing, has predicted that by 2015, a single socket will contain hundreds of cores. (http://www.accessmylibrary.com/coms2/summary_0286-30177016_ITM)

There have also been strong trends towards cluster and grid computing, which seek to take advantage of multiple, low cost (commodity) computer systems and treat them as a logical entity. Several categories of clusters exists, ranging from high performance computers linked together via high speed interconnects, to geographically separated systems linked together over the Internet. (http://en.wikipedia.org/wiki/Cluster_computing) Grid computing is a form of the latter, generally composed of multiple "collections" of computers (grid elements) that do not necessarily trust each other.

Putting these together, we see a clear movement towards commodity processors in both the areas of parallel computing (processors in a single computer system) and distributed computing (using multiple computer systems). Perhaps the strongest driving force behind these trends is one of supply and demand, or economies of scale. Specialized hardware is, by definition, in less demand then general purpose hardware, making it much more difficult to recover design and production costs. Hence, there is a strong economic incentive for consumers and manufacturers alike to favor more general purpose solutions.

Despite these trends, the "traditional" supercomputer is alive and well. Today's highest performance machines are capable of performing hundreds of teraflops per second. (A teraflop is 1 x 10^12 FLOPS.) As of June 2007, the world's fastest computer, as measured by the Linpack (http://en.wikipedia.org/wiki/Linpack) benchmark, is IBM's massively parallel Blue Gene/L. IBM has plans to build a 3 petaflop (3 x 10^15 FLOPS) machine by fall 2007, and a 10 petaflop machine in the 2010-2012 timeframe. More information on IBM's Blue Gene and other supercomputers can be found at http://www.top500.org/.

== Software Trends ==
With dramatic increases in hardware performance come more demanding applications, which in turn demands higher performance software. Many scientific applications available today, some even commercially, were not available on general purpose architectures even a few years ago.

'''Mathematica 6''' by Wolfram Research, is one of a growing number of commercially available scientific/engineering applications. Mathematica does not require parallel processors, but does require significant resources (at least, from the "average" personal computer) - at least 512mb memory. However, on many operating systems Mathematica is able to take advantage of multiple processors, focusing on linear algebra and machine-precision real numbers. Wolfram does offer a parallel computing toolkit (http://www.wolfram.com/products/applications/parallel) that allows Mathematica application designers to take advantage of various parallel architectures, ranging from shared memory multiprocessor machines to supercomputers. Wolfram also offers a version of Mathematica tailored to cluster/grid computing, see http://www.wolfram.com/products/gridmathematica/.

There is a trend in HPC towards virtualization. Virtualization allows application programmers to write applications for virtual machines, not concerning themselves with physical platforms. There are many benefits to running on virtual machines, among them the ability to seamlessly migrate the virtual machines (along with its running applications) off its physical host machine. However, in practice there are many challenges related to virtualization, chief among them the performance limitations they impose (http://www.scientificcomputing.com/ShowPR~PUBCODE~030~ACCT~3000000100~ISSUE~0707~RELTYPE~HPCC~PRODCODE~00000000~PRODLETT~C.html).

== Grand Challenge Problems ==
Some problems are so complex that to solve them would require a significant increase (in some cases by orders of magnitude) in the current computational capabilities of today's computers. These problems are loosely defined as "Grand Challenge Problems." Grand Challenge problems are problems that are solvable, but not in a reasonable period of time on today's computers. Further, a grand challenge problem is a problem of some importance, either socially or economically.

Computational modeling/simulation: why, benefits. in-depth analysis can be performed cheaply on hypothetical designs.
There is a direct correlation between computational performance and the problems that can be studied through simulation.

'''Biology''' - Human Genome Project (http://en.wikipedia.org/wiki/Human_genome_project)
Looks like a "divide and conquer" approach. The genome was broken down into smaller pieces, approximately 150,000 base pairs in length, processed separately, then assembled to form chromosones.

'''Physics''' (nuclear technology)

'''Astronomy'''

'''Cognition/Strong AI''' - the idea that computers can become "self aware." (vs. weak AI who's goal is not so grandiose - Turing test)

'''Game playing''' - chess, checkers (Jonathon Schaefer)

Linpack benchmark

----

Links:
http://en.wikipedia.org/wiki/High_Performance_Computing

http://www.top500.org/

http://en.wikipedia.org/wiki/Grand_Challenge_problem

http://en.wikipedia.org/wiki/Grand_Challenge

CSC/ECE 506 Fall 2007/wiki1 2 3K8i

2007-09-04T00:32:39Z

Jfswaffo:

== Trends in Scientific and Engineering Computing ==

Scientific and engineering applications continue to demand the highest performance computers available, a trend established in the early days of supercomputers that continues today in the realm of "High Performance Computing" (HPC). As problems are solved, new, more complex problems arise to take their place. Many Grand Challenge Problems "on the radar" today were not feasible on the supercomputers of a just decade ago. Generally, each successive generation of Grand Challenge problems require more memory and faster processing capabilities. The architectures used to deliver those memory and processing speed requirements are changing, and along with them the algorithms and techniques used to make efficient use of them.

Before looking at some of today's most challenging computational problems, it may be instructive to look at the trends in HPC over the last decade or so.

== Hardware Trends ==
According the the U.S. Army Research Laboratory (http://www.arl.army.mil/www/default.cfm?Action=20&Page=272), there have been five generations of architectures in the realm of scientific computing. They are serial processors (1947-1986), vector processors (1986-2002), shared memory (1993-present), distributed memory (2000-present), and commodity clusters (2001-present).

Indeed, the trend in recent years in multiprocessing has been away from vector architectures and towards low cost, multi-threaded single address spaced systems. (http://www.nus.edu.sg/comcen/svu/publications/SVULink/vol_1_iss_1/hpc-trends.html) Multi-core processors are becoming more and more mainstream. Today, many new desktop systems contain dual cores, with some quad cores being sold. Tony Hey (http://en.wikipedia.org/wiki/Tony_Hey), a leading researcher in parallel computing, has predicted that by 2015, a single socket will contain hundreds of cores. (http://www.accessmylibrary.com/coms2/summary_0286-30177016_ITM)

There have also been strong trends towards cluster and grid computing, which seek to take advantage of multiple, low cost (commodity) computer systems and treat them as a logical entity. Several categories of clusters exists, ranging from high performance computers linked together via high speed interconnects, to geographically separated systems linked together over the Internet. (http://en.wikipedia.org/wiki/Cluster_computing) Grid computing is a form of the latter, generally composed of multiple "collections" of computers (grid elements) that do not necessarily trust each other.

Putting these together, we see a clear movement towards commodity processors in both the areas of parallel computing (processors in a single computer system) and distributed computing (using multiple computer systems). Perhaps the strongest driving force behind these trends is one of supply and demand, or economies of scale. Specialized hardware is, by definition, in less demand then general purpose hardware, making it much more difficult to recover design and production costs. Hence, there is a strong economic incentive for consumers and manufacturers alike to favor more general purpose solutions.

Despite these trends, the "traditional" supercomputer is alive and well. Today's highest performance machines are capable of performing hundreds of teraflops per second. (A teraflop is 1 x 10^12 FLOPS.) As of June 2007, the world's fastest computer, as measured by the Linpack (http://en.wikipedia.org/wiki/Linpack) benchmark, is IBM's massively parallel Blue Gene/L. IBM has plans to build a 3 petaflop (3 x 10^15 FLOPS) machine by fall 2007, and a 10 petaflop machine in the 2010-2012 timeframe. More information on IBM's Blue Gene and other supercomputers can be found at http://www.top500.org/.

== Software Trends ==
With dramatic increases in hardware performance come more demanding applications, which in turn demands higher performance software. Many scientific applications available today, some even commercially, were not available on general purpose architectures even a few years ago.

'''Mathematica 6''' by Wolfram Research, is one of a growing number of commercially available scientific/engineering applications. Mathematica does not require parallel processors, but does require significant resources (at least, from the "average" personal computer) - at least 512mb memory. However, on many operating systems Mathematica is able to take advantage of multiple processors, focusing on linear algebra and machine-precision real numbers. Wolfram does offer a parallel computing toolkit (http://www.wolfram.com/products/applications/parallel) that allows Mathematica application designers to take advantage of various parallel architectures, ranging from shared memory multiprocessor machines to supercomputers. Wolfram also offers a version of Mathematica tailored to cluster/grid computing, see http://www.wolfram.com/products/gridmathematica/.

There is a trend in HPC towards virtualization. Virtualization allows application programmers to write applications for virtual machines, not concerning themselves with the physical platforms. There are many benefits to running on virtual machines, amonth them the ability to seamlessly migrate the virtual machines (along with its running applications) off its physical host machine. However, in practice there are many challenges related to virtualization, chief among them the performance limitations they impose (http://www.scientificcomputing.com/ShowPR~PUBCODE~030~ACCT~3000000100~ISSUE~0707~RELTYPE~HPCC~PRODCODE~00000000~PRODLETT~C.html).

== Grand Challenge Problems ==
Some problems are so complex that to solve them would require a significant increase (in some cases by orders of magnitude) in the current computational capabilities of today's computers. These problems are loosely defined as "Grand Challenge Problems." Grand Challenge problems are problems that are solvable, but not in a reasonable period of time on today's computers. Further, a grand challenge problem is a problem of some importance, either socially or economically.

Computational modeling/simulation: why, benefits. in-depth analysis can be performed cheaply on hypothetical designs.
There is a direct correlation between computational performance and the problems that can be studied through simulation.

'''Biology''' - Human Genome Project (http://en.wikipedia.org/wiki/Human_genome_project)
Looks like a "divide and conquer" approach. The genome was broken down into smaller pieces, approximately 150,000 base pairs in length, processed separately, then assembled to form chromosones.

'''Physics''' (nuclear technology)

'''Astronomy'''

'''Cognition/Strong AI''' - the idea that computers can become "self aware." (vs. weak AI who's goal is not so grandiose - Turing test)

'''Game playing''' - chess, checkers (Jonathon Schaefer)

Linpack benchmark

----

Links:
http://en.wikipedia.org/wiki/High_Performance_Computing

http://www.top500.org/

http://en.wikipedia.org/wiki/Grand_Challenge_problem

http://en.wikipedia.org/wiki/Grand_Challenge

CSC/ECE 506 Fall 2007/wiki1 2 3K8i

2007-09-04T00:31:35Z

Jfswaffo:

== Trends in Scientific and Engineering Computing ==

Scientific and engineering applications continue to demand the highest performance computers available, a trend established in the early days of supercomputers that continues today in the realm of "High Performance Computing" (HPC). As problems are solved, new, more complex problems arise to take their place. Many Grand Challenge Problems "on the radar" today were not feasible on the supercomputers of a just decade ago. Generally, each successive generation of Grand Challenge problems require more memory and faster processing capabilities. The architectures used to deliver those memory and processing speed requirements are changing, and along with them the algorithms and techniques used to make efficient use of them.

Before looking at some of today's most challenging computational problems, it may be instructive to look at the trends in HPC over the last decade or so.

== Hardware Trends ==
According the the U.S. Army Research Laboratory (http://www.arl.army.mil/www/default.cfm?Action=20&Page=272), there have been five generations of architectures in the realm of scientific computing. They are serial processors (1947-1986), vector processors (1986-2002), shared memory (1993-present), distributed memory (2000-present), and commodity clusters (2001-present).

Indeed, the trend in recent years in multiprocessing has been away from vector architectures and towards low cost, multi-threaded single address spaced systems. (http://www.nus.edu.sg/comcen/svu/publications/SVULink/vol_1_iss_1/hpc-trends.html) Multi-core processors are becoming more and more mainstream. Today, many new desktop systems contain dual cores, with some quad cores being sold. Tony Hey (http://en.wikipedia.org/wiki/Tony_Hey), a leading researcher in parallel computing, has predicted that by 2015, a single socket will contain hundreds of cores. (http://www.accessmylibrary.com/coms2/summary_0286-30177016_ITM)

There have also been strong trends towards cluster and grid computing, which seek to take advantage of multiple, low cost (commodity) computer systems and treat them as a logical entity. Several categories of clusters exists, ranging from high performance computers linked together via high speed interconnects, to geographically separated systems linked together over the Internet. (http://en.wikipedia.org/wiki/Cluster_computing) Grid computing is a form of the latter, generally composed of multiple "collections" of computers (grid elements) that do not necessarily trust each other.

Putting these together, we see a clear movement towards commodity processors in both the areas of parallel computing (processors in a single computer system) and distributed computing (using multiple computer systems). Perhaps the strongest driving force behind these trends is one of supply and demand, or economies of scale. Specialized hardware is, by definition, in less demand then general purpose hardware, making it much more difficult to recover design and production costs. Hence, there is a strong economic incentive for consumers and manufacturers alike to favor more general purpose solutions.

Despite these trends, the "traditional" supercomputer is alive and well. Today's highest performance machines are capable of performing hundreds of teraflops per second. (A teraflop is 1 x 10^12 FLOPS.) As of June 2007, the world's fastest computer, as measured by the Linpack (http://en.wikipedia.org/wiki/Linpack) benchmark, is IBM's massively parallel Blue Gene/L. IBM has plans to build a 3 petaflop (3 x 10^15 FLOPS) machine by fall 2007, and a 10 petaflop machine in the 2010-2012 timeframe. More information on IBM's Blue Gene and other supercomputers can be found at http://www.top500.org/.

== Software Trends ==
With dramatic increases in hardware performance come more demanding applications, which in turn demands higher performance software. Many scientific applications available today, some even commercially, were not available on general purpose architectures even a few years ago.

'''Mathematica 6''' by Wolfram Research, is one of a growing number of commercially available scientific/engineering applications. Mathematica does not require parallel processors, but does require significant resources (at least, from the "average" personal computer) - at least 512mb memory. However, on many operating systems Mathematica is able to take advantage of multiple processors, focusing on linear algebra and machine-precision real numbers. Wolfram does offer a parallel computing toolkit (http://www.wolfram.com/products/applications/parallel) that allows Mathematica application designers to take advantage of various parallel architectures, ranging from shared memory multiprocessor machines to supercomputers. Wolfram also offers a version of Mathematic tailored to cluster/grid computing, see http://www.wolfram.com/products/gridmathematica/.

There is a trend in HPC towards virtualization. Virtualization allows application programmers to write applications for virtual machines, not concerning themselves with the physical platforms. There are many benefits to running on virtual machines, amonth them the ability to seamlessly migrate the virtual machines (along with its running applications) off its physical host machine. However, in practice there are many challenges related to virtualization, chief among them the performance limitations they impose (http://www.scientificcomputing.com/ShowPR~PUBCODE~030~ACCT~3000000100~ISSUE~0707~RELTYPE~HPCC~PRODCODE~00000000~PRODLETT~C.html).

== Grand Challenge Problems ==
Some problems are so complex that to solve them would require a significant increase (in some cases by orders of magnitude) in the current computational capabilities of today's computers. These problems are loosely defined as "Grand Challenge Problems." Grand Challenge problems are problems that are solvable, but not in a reasonable period of time on today's computers. Further, a grand challenge problem is a problem of some importance, either socially or economically.

Computational modeling/simulation: why, benefits. in-depth analysis can be performed cheaply on hypothetical designs.
There is a direct correlation between computational performance and the problems that can be studied through simulation.

'''Biology''' - Human Genome Project (http://en.wikipedia.org/wiki/Human_genome_project)
Looks like a "divide and conquer" approach. The genome was broken down into smaller pieces, approximately 150,000 base pairs in length, processed separately, then assembled to form chromosones.

'''Physics''' (nuclear technology)

'''Astronomy'''

'''Cognition/Strong AI''' - the idea that computers can become "self aware." (vs. weak AI who's goal is not so grandiose - Turing test)

'''Game playing''' - chess, checkers (Jonathon Schaefer)

Linpack benchmark

----

Links:
http://en.wikipedia.org/wiki/High_Performance_Computing

http://www.top500.org/

http://en.wikipedia.org/wiki/Grand_Challenge_problem

http://en.wikipedia.org/wiki/Grand_Challenge

CSC/ECE 506 Fall 2007/wiki1 2 3K8i

2007-09-04T00:12:36Z

Jfswaffo:

== Trends in Scientific and Engineering Computing ==

Scientific and engineering applications continue to demand the highest performance computers available, a trend established in the early days of supercomputers that continues today in the realm of "High Performance Computing" (HPC). As problems are solved, new, more complex problems arise to take their place. Many Grand Challenge Problems "on the radar" today were not feasible on the supercomputers of a just decade ago. Generally, each successive generation of Grand Challenge problems require more memory and faster processing capabilities. The architectures used to deliver those memory and processing speed requirements are changing, and along with them the algorithms and techniques used to make efficient use of them.

Before looking at some of today's most challenging computational problems, it may be instructive to look at the trends in HPC over the last decade or so.

== Hardware Trends ==
According the the U.S. Army Research Laboratory (http://www.arl.army.mil/www/default.cfm?Action=20&Page=272), there have been five generations of architectures in the realm of scientific computing. They are serial processors (1947-1986), vector processors (1986-2002), shared memory (1993-present), distributed memory (2000-present), and commodity clusters (2001-present).

Indeed, the trend in recent years in multiprocessing has been away from vector architectures and towards low cost, multi-threaded single address spaced systems. (http://www.nus.edu.sg/comcen/svu/publications/SVULink/vol_1_iss_1/hpc-trends.html) Multi-core processors are becoming more and more mainstream. Today, many new desktop systems contain dual cores, with some quad cores being sold. Tony Hey (http://en.wikipedia.org/wiki/Tony_Hey), a leading researcher in parallel computing, has predicted that by 2015, a single socket will contain hundreds of cores. (http://www.accessmylibrary.com/coms2/summary_0286-30177016_ITM)

There have also been strong trends towards cluster and grid computing, which seek to take advantage of multiple, low cost (commodity) computer systems and treat them as a logical entity. Several categories of clusters exists, ranging from high performance computers linked together via high speed interconnects, to geographically separated systems linked together over the Internet. (http://en.wikipedia.org/wiki/Cluster_computing) Grid computing is a form of the latter, generally composed of multiple "collections" of computers (grid elements) that do not necessarily trust each other.

Putting these together, we see a clear movement towards commodity processors in both the areas of parallel computing (processors in a single computer system) and distributed computing (using multiple computer systems). Perhaps the strongest driving force behind these trends is one of supply and demand, or economies of scale. Specialized hardware is, by definition, in less demand then general purpose hardware, making it much more difficult to recover design and production costs. Hence, there is a strong economic incentive for consumers and manufacturers alike to favor more general purpose solutions.

Despite these trends, the "traditional" supercomputer is alive and well. Today's highest performance machines are capable of performing hundreds of teraflops per second. (A teraflop is 1 x 10^12 FLOPS.) As of June 2007, the world's fastest computer, as measured by the Linpack (http://en.wikipedia.org/wiki/Linpack) benchmark, is IBM's massively parallel Blue Gene/L. IBM has plans to build a 3 petaflop (3 x 10^15 FLOPS) machine by fall 2007, and a 10 petaflop machine in the 2010-2012 timeframe. More information on IBM's Blue Gene and other supercomputers can be found at http://www.top500.org/.

== Software Trends ==
With dramatic increases in hardware performance come more demanding applications, which in turn demands higher performance software. Many scientific applications available today, some even commercially, were not available on general purpose architectures even a few years ago.

'''Mathematica 6''' by Wolfram Research, is a commercially available scientific/engineering application that does not require parallel processors, but does require significant resources (at least, from the "average" personal computer) - at least 512mb memory. However, on many operating systems Mathematica is able to take advantage of multiple processors, focusing on linear algebra and machine-precision real numbers. Wolfram does offer a parallel computing toolkit (http://www.wolfram.com/products/applications/parallel) that allows Mathematica application designers to take advantage of various parallel architectures, ranging from shared memory multiprocessor machines to supercomputers. Wolfram also offers a version of Mathematic tailored to cluster/grid computing, see http://www.wolfram.com/products/gridmathematica/.

Some challenges today in keeping the "performance" in HPC (High Performance Computing):
http://www.scientificcomputing.com/ShowPR~PUBCODE~030~ACCT~3000000100~ISSUE~0707~RELTYPE~HPCC~PRODCODE~00000000~PRODLETT~C.html
All is not well in HPC. There is a tend towards virtualization, or running on virtual machines. One benefit of this approach is that the virtual machine can be seamlessly migrated off its physical host machine. However, in practice there are many challenges related to virtualization. Current designs impose some performance limitations on HPC.
<examples, source>

Petascale computing - 10^15 floating point operations per second! Should be a reality by 2010 (http://www.nsf.gov/pubs/2005/nsf05625/nsf05625.htm).

Computational modeling/simulation: why, benefits. in-depth analysis can be performed cheaply on hypothetical designs.
There is a direct correlation between computational performance and the problems that can be studied through simulation.

== Grand Challenge Problems ==
// todo: work on wording below 
Some problems are so complex that to solve them would require a significant increase (in some cases by orders of magnitude) in the current computational capabilities of today's computers. These problems are loosely defined as "Grand Challenge Problems." Grand Challenge problems are problems that are solvable, but not in a reasonable period of time on today's computers. Further, a grand challenge problem is a problem of some importance, either socially or economically.

'''Biology''' - Human Genome Project (http://en.wikipedia.org/wiki/Human_genome_project)
Looks like a "divide and conquer" approach. The genome was broken down into smaller pieces, approximately 150,000 base pairs in length, processed separately, then assembled to form chromosones.

'''Physics''' (nuclear technology)

'''Astronomy'''

'''Cognition/Strong AI''' - the idea that computers can become "self aware." (vs. weak AI who's goal is not so grandiose - Turing test)

'''Game playing''' - chess, checkers (Jonathon Schaefer)

Linpack benchmark

----

Links:
http://en.wikipedia.org/wiki/High_Performance_Computing

http://www.top500.org/

http://en.wikipedia.org/wiki/Grand_Challenge_problem

http://en.wikipedia.org/wiki/Grand_Challenge

CSC/ECE 506 Fall 2007/wiki1 2 3K8i

2007-09-03T23:56:38Z

Jfswaffo:

CSC/ECE 506 Fall 2007/wiki1 2 3K8i

2007-09-03T23:56:15Z

Jfswaffo:

CSC/ECE 506 Fall 2007/wiki1 2 3K8i

2007-09-03T23:54:10Z

Jfswaffo:

CSC/ECE 506 Fall 2007/wiki1 2 3K8i

2007-09-03T23:46:43Z

Jfswaffo:

CSC/ECE 506 Fall 2007/wiki1 2 3K8i

2007-09-03T23:38:07Z

Jfswaffo:

CSC/ECE 506 Fall 2007/wiki1 2 3K8i

2007-09-03T23:37:50Z

Jfswaffo:

CSC/ECE 506 Fall 2007/wiki1 2 3K8i

2007-09-03T22:49:27Z

Jfswaffo:

CSC/ECE 506 Fall 2007/wiki1 2 3K8i

2007-09-03T22:44:50Z

Jfswaffo: