Expertiza_Wiki - User contributions [en]

E1735. UI changes for review and score reports

2017-04-13T03:46:55Z

Remcelfr: /* Test Plan */

==Introduction==
This wiki provides details on the tasks that were undertaken as part of the continuous improvement to the Expertiza project.
===Background===
[[Expertiza_documentation|Expertiza]] is a web application where students can submit and peer-review learning objects (articles, code, web sites, etc). The application provides a complete system through which students and instructors collaborate on the learning objects as well as submit, review and grade assignments for the courses. It is used in select courses at NC State and by professors at several other colleges and universities. The Expertiza project is supported by the National Science Foundation.

===Overview of Review Functionality===

The Expertiza review system encompasses many types of reviews. Assignments can have multiple submission rounds defined with their own due dates and criteria. Each round can have an associated questionnaire whereby peers are encouraged, or required, to review each others' submissions and rate those submissions using the scores 1 through 5 for each question. The scores for each question are averaged to find the rating for the submission for each questionnaire response. The average of all questionnaire responses determine the score for the submission.After the reviews are submitted, the recipient of those reviews can rate the reviewers using a similar questionnaire. On this questionnaire, the author of the submission will rate the reviews based on the reviewers understanding, helpfulness, and respectfulness. This is a review of the reviews, thus it is termed a "metareview."

Both students and instructors using Expertiza have the ability to view the reviews and the scores associated with the reviews for each assignment. These screens will display review summary and detail information in various formats such as lists, graphs, and heatgrids. The instructor will be able to see all review and score information for all teams on the assignment whereas a student will only be able to see the review and score information pertaining to them.

The reviews and associated scores are available on the scores report. To access the score reports in Expertiza follow these instructions:

'''As a student'''

# Log into Expertiza.
# Click on the 'Assignments' link on the top navigation bar.
# Find the assignment in the list and click the title of the assignment.
# Click on the 'Your scores' link to see the standard view or click on the 'Alternate View' link to see the heatgrid view.

'''As an instructor'''

# Log into Expertiza.
# Hover over the 'Manage' item on the top navigation bar, then select click the 'Assignments' link.
# Find the assignment in the list and click the 'View scores' icon (a star with a magnifying glass) in the 'Actions' column.
# This will bring up the standard view. To see the heatgrid view, click the 'Alternate View' link on the team headings or click the 'view heatgrid' beneath the 'Final Score' when the team is expanded.

===Motivation===
By participating in the overall refactoring effort as part of the continuous improvement of Expertiza, students get an opportunity to work on a open source software project. This helps them gain exposure on the technologies used in the project as well as much needed experience in collaborating with peers as part of the software development process. This effort was undertaken as a final project for the CSC 517 - Object Oriented Design and Development course at North Carolina State University in the spring of 2017.

==Project Purpose==

===Requirements Statement===
Expertiza displays reviews (i) to the team who was reviewed, and (ii) to the reviewer. A student user can see all the reviews of his/her team’s project. The instructor can see all the reviews of everyone’s project. The instructor also has access to a review report, which shows, for each reviewer, all the reviews that (s)he wrote. Currently, the score report and review report use completely different code. This makes the UI non-orthogonal and also causes DRY problems. So, we would like to have a single way of displaying reviews that would be visible to students (reviews that they did, and reviews that their team received), and instructors (reviews that each time received, sorted by team; and reviews that each student did, sorted by student).

===Required Tasks===
The tasks involved as part of this requirements change are as follows:
# Compact the review display
#* Eliminate the blank lines between items within a single review. Instead vary the background color from line to line to improve readability
#* With a single click, there should be a way to hide all the reviews, reveal just the headings (as at present), or expand all the reviews
# At the top of each review, it should say
#* Who submitted the review. The instructor should see the user’s name and user-ID.
#* A student should see
#** “Reviewer #k”, where k is an integer between 1 and n, the number of reviews that have been submitted for this project
#** The version number of the review
#** The time the review was submitted
# There should be a tabbed view to switch between various review views
#* One tab has overall statistics (averages, min, max, as the present “normal” view)
#* One tab has the heat map (current “alternate” view)
#* One tab has a grid view, with no scores, but text comments in the grid squares, and then a “More” link to display the whole comment (which will require expanding the row of the grid)
#* Switching between reviews from Reviewer k and Reviewer j might also be done by clicking on different tabs. Or, it might be more convenient to keep the current score view, which lists the n reviews across the page. Then the student should be able to click on the reviewer number (the instructor would instead click on the reviewer name) and see the review done by that reviewer
# To make it easy to focus on the reviewer’s feedback, there should be a way to hide and/or gray the criteria (“questions”), so the responses stand out more clearly
# There needs to be a way to search all reviews (of a particular project, or by a particular individual) for a given text string. The user should be able to go from one instance of the text string to another by clicking down and up buttons

===Problem Statement===
In the current state, the score report for instructors and students are built differently though they display the same information using similar UI elements. The application has multiple views into the same information but the way in which those views are accessed, the code which populates them, and the layout of the screens differs unnecessarily between instructors and students and across the views themselves. This leads to redundant code in both the backend and frontend of the application. Furthermore, since the UI is not uniform between instructors and students, instructors may have difficulty assisting students in accessing their score information due to the differences which are present in the UI that leads to confusion.

Following are some of the issues with the current state UI which we seek to rectify.

====Scores Report====
[[File:Problem_Statement_Diagram_1A_-_Instructor_View_-_65.png]]

The scores report for students and instructors have very similar layouts despite being created by different controller methods and views. They both display graphs, reviews on team submissions, author feedback, and score metrics. The primary different between them is that the instructor view (shown above) displays information for all teams in a collapsible accordion widget format while the student view (shown below) display the information only for a single team. There are some further discontinuities between the two UIs. For example, the student cannot access the heatgrid view from within the scores report page. This view is only accessible from the assignment page for students. For instructors there are two ways to access the heatgrid view from a single page. The 'Alternate View' link is adjacent to the team name on the heading bar and there is also a link inexplicably placed beneath the 'Final Score' field.

[[File:Problem_Statement_Diagram_1B_-_Student_View_-_65.png]]

====Author Feedback====
Author feedback takes two different forms when being shown to instructors but only one form for students. Both students and instructors have access to the author feedback format shown on the left in the student view. This format is identical to the format of the review scores and is displayed on the scores report for both instructor and student. The format on the right is shown on the heatgrid view yet it is only available to instructors. The information conveyed by these two formats is nearly identical and not uniformly available to all consumers of this information.

[[File:Problem_Statement_Diagram_2_-_Author_Feedback_-_65.png]]

====Graphs and Charts====
The scores report view has a bar of graphs and charts at the top of the page for both students and instructors. Both views shown below use a donut chart and bar graphs though their method of display is not uniform. The instructor view has titles beneath each item but the student view does not. The 'Submitted work' and 'Author Feedback' titles shown, despite being beneath the bar graphs, are actually headings for the metrics which are displayed beneath the graphs. Also, the graphs contain two labels on the y-axis: the maximum score and the average score. The graphs are so compact that the values on the axis overlap and make them illegible.

[[File:Problem_Statement_Diagram_3_-_Squashed_Graphs_-_65.png]]

==Project Design==

===High Level Design===

====Design Overview====
The project requirements state that we need to create a standard UI for accessing and consuming review and score information. The emphasis will be on smart and purposeful code reuse as well as ease of navigation to access information. To achieve these results we will redesign the scores report to work for both instructors and students alike. There will be a single route, a single controller method, and a single view that is common t users of both role types. In some instances, such as with the graphs and charts, the data will be different enough to warrant separate methods to retrieve the values needed. In most instances, the data is identical and will be accessed identically.

We will create a standard hierarchy which works for both students (who only need to see a single team's scores) and instructors (who need to see all teams' scores). This hierarchy will be rendered within a page in the form of a set of tabbed panes which contain the contents. We will separate the information among four tabs.

# Reviews and scores
# Author Feedback
# Graphs and Charts
# Heatgrid

Putting these components on different tabs will allow us to de-clutter the UI. The instructor scores report UI has multiple ways to expand and collapse sections of information, links are placed in some unusual places, and the page can get so cluttered that it is difficult to distinguish one thing from another. This will be cleaned up by removing some links, removing the author feedback and the charts, and placing the reviews and scores into more discernible sections. The graphs and charts will be on their own tab so they can be larger and easier to read. Since they are not confined to a single bar of a fixed height new graphs and charts can be added. The heatgrid will no longer be coupled with the author feedback and there will be a standard author feedback view which encompasses all information needs. Each of these tabs will be rendered using their own partial.

To prevent the application from pulling data for tabs which the user will not view, AJAX calls will be used to access the data on demand without reloading the page. These calls can also be expanded to request data for individual sections. Routes will be created to controller methods specifically to pull the data for each tab so that calls can be made to them to generate the necessary data structures. These will be accessed when a user expands a group or switches tabs.

====Technologies Used====

{| class="wikitable"
|-
! Technology
! Technology Type
! Use(s)
|-
| Ruby
| Language
| Core development of the application's backend system
|-
| Rails
| Framework
| Implements MVC; CRUD support; Web application support
|-
| RSpec (rspec)
| Gem
| Enables TDD; supports testing DSL
|-
| JQuery (jquery.ui.tabs)
| Library
| Enables creation of tabbed Web interfaces
|-
| JQuery (jquery.ui.accordion)
| Library
| Enables creation of accordion widgets for Web interfaces
|-
| Sass (sass-rails)
| Gem
| Sass style sheet pre-processor engine
|-
| Cascading Style Sheets (CSS)
| Language
| Web page presentation description language
|-
| Sassy CSS (SCSS)
| Language
| Superset of CSS style sheet language
|-
| rails-ajax
| Gem
| Enable AJAX to refresh containers within views without reloading the page
|}

====Software Patterns====

'''Model-View-Controller (MVC)''' - MVC is a software architectural pattern which divides an application into three parts which separate the data representation from the interface through which users will access and operate on the data. The main components of this pattern are the:
* Model - The underlying logical structure of the application's data along with the accesses and operators on the data in the persistent storage medium.
* View - The user facing representation of the data along with the means for the user to request, operate on, or view the data.
* Controller - The intermediary layer between the Model and the View which accepts requests from the View, translates that to the Model, receives the Model's response and formats the response to the View.

'''Active Record''' - A software architectural pattern which wraps data from persistent storage, along with the method to operate on the data, in a class or object of a class to be used within an application. It uses the object-relation mapping (ORM) technique to create virtual database objects.

===Low Level Design===

====Screen Mockups====

'''New Scores Report With Multiple Teams and Collapsed Reviews'''

[[File:Expanded_Teams_With_Collapsed_Tabs_-_45.png]]

'''New Scores Report With Multiple Teams and Expanded Reviews'''

[[File:Expanded_Teams_With_Expanded_Tabs_-_85.png]]

==Test Plan==
For testing, we built off the existing test framework which implemented RSPEC. The goal of our testing is to verify that the existing functionality is still present in the new views and is accessible to both the student and the instructor. Below are the tests that have been modified or created to verify the changed functionality. Any other tests not listed below are assumed to be unmodified and are intended to still work with the new updates. Note that some requirements of this project cannot be verified with the script such as formatting changes, but any functional modifications to the layout will be verified.

{| class="wikitable"
! colspan="2" | Test Case 1
|-
! Test Type
| Functional
|-
! Scenario
| Test to see if modifications to the display_as_html function in response.rb order to hide the “feedback review” button is correct for a student
|-
! Pre-Conditions
|
Make sure student to test with has the following:
#Has one course assigned
#Has one assigned as part of that course
#Has more than one review for that assignment
|-
! Description
|
#Login to the site as a student
#Click on "Assignments" on the top menu
#Select an assignment from the list
#On the "Submit or Review work for Expertiza" screen, click on "Your scores”
#On the "Summary Report for assignment" screen, verify that the "Give feedback for Review 1" button is not present
|-
| colspan="2" |  
|-
! colspan="2" | Test Case 2
|-
! Test Type
| Functional
|-
! Scenario
| Test to see if modifications to the display_as_html function in response.rb order to show the “feedback review” button is correct for a student
|-
! Pre-Conditions
|
Make sure student to test with has the following:
#Has one course assigned
#Has one assigned as part of that course
#Has more than one review for that assignment
|-
! Description
|
#Login to the site as a student
#Click on "Assignments" on the top menu
#Select an assignment from the list
#On the "Submit or Review work for Expertiza" screen, click on "Your scores”
#On the “Summary Report for assignment” screen, select the “Show Review” button
#On the "Summary Report for assignment" screen, verify that the "Give feedback for Review 1" button is present
|-
| colspan="2" |  
|-
! colspan="2" | Test Case 3
|-
! Test Type
| Functional
|-
! Scenario
| Test to see if modifications to the display_as_html function in response.rb order to hide the “feedback review” button is correct for an instructor
|-
! Pre-Conditions
|
Make sure student to test with has the following:
#At least one assignment exists
#Has more than one review for that assignment
|-
! Description
|
#Login to the site as an instructor
#Click on "Manage" on the top menu
#Click on “Assignments”
#Select an assignment from the list
#Click on "View Scores”
#On the "Summary Report for assignment" screen, verify that the "Give feedback for Review 1" button is not present
|-
| colspan="2" |  
|-
! colspan="2" | Test Case 4
|-
! Test Type
| Functional
|-
! Scenario
| Test to see if modifications to the display_as_html function in response.rb order to show the “feedback review” button is correct for an instructor
|-
! Pre-Conditions
|
Make sure student to test with has the following:
#At least one assignment exists
#Has more than one review for that assignment
|-
! Description
|
#Login to the site as an instructor
#Click on "Manage" on the top menu
#Click on “Assignments”
#Select an assignment from the list
#Click on "View Scores”
#On the “Summary Report for assignment” screen, select the “Show Review” button
#On the "Summary Report for assignment" screen, verify that the "Give feedback for Review 1" button is present
|-
| colspan="2" |  

E1735. UI changes for review and score reports

2017-04-13T03:45:50Z

Remcelfr:

==Introduction==
This wiki provides details on the tasks that were undertaken as part of the continuous improvement to the Expertiza project.
===Background===
[[Expertiza_documentation|Expertiza]] is a web application where students can submit and peer-review learning objects (articles, code, web sites, etc). The application provides a complete system through which students and instructors collaborate on the learning objects as well as submit, review and grade assignments for the courses. It is used in select courses at NC State and by professors at several other colleges and universities. The Expertiza project is supported by the National Science Foundation.

===Overview of Review Functionality===

The Expertiza review system encompasses many types of reviews. Assignments can have multiple submission rounds defined with their own due dates and criteria. Each round can have an associated questionnaire whereby peers are encouraged, or required, to review each others' submissions and rate those submissions using the scores 1 through 5 for each question. The scores for each question are averaged to find the rating for the submission for each questionnaire response. The average of all questionnaire responses determine the score for the submission.After the reviews are submitted, the recipient of those reviews can rate the reviewers using a similar questionnaire. On this questionnaire, the author of the submission will rate the reviews based on the reviewers understanding, helpfulness, and respectfulness. This is a review of the reviews, thus it is termed a "metareview."

Both students and instructors using Expertiza have the ability to view the reviews and the scores associated with the reviews for each assignment. These screens will display review summary and detail information in various formats such as lists, graphs, and heatgrids. The instructor will be able to see all review and score information for all teams on the assignment whereas a student will only be able to see the review and score information pertaining to them.

The reviews and associated scores are available on the scores report. To access the score reports in Expertiza follow these instructions:

'''As a student'''

# Log into Expertiza.
# Click on the 'Assignments' link on the top navigation bar.
# Find the assignment in the list and click the title of the assignment.
# Click on the 'Your scores' link to see the standard view or click on the 'Alternate View' link to see the heatgrid view.

'''As an instructor'''

# Log into Expertiza.
# Hover over the 'Manage' item on the top navigation bar, then select click the 'Assignments' link.
# Find the assignment in the list and click the 'View scores' icon (a star with a magnifying glass) in the 'Actions' column.
# This will bring up the standard view. To see the heatgrid view, click the 'Alternate View' link on the team headings or click the 'view heatgrid' beneath the 'Final Score' when the team is expanded.

===Motivation===
By participating in the overall refactoring effort as part of the continuous improvement of Expertiza, students get an opportunity to work on a open source software project. This helps them gain exposure on the technologies used in the project as well as much needed experience in collaborating with peers as part of the software development process. This effort was undertaken as a final project for the CSC 517 - Object Oriented Design and Development course at North Carolina State University in the spring of 2017.

==Project Purpose==

===Requirements Statement===
Expertiza displays reviews (i) to the team who was reviewed, and (ii) to the reviewer. A student user can see all the reviews of his/her team’s project. The instructor can see all the reviews of everyone’s project. The instructor also has access to a review report, which shows, for each reviewer, all the reviews that (s)he wrote. Currently, the score report and review report use completely different code. This makes the UI non-orthogonal and also causes DRY problems. So, we would like to have a single way of displaying reviews that would be visible to students (reviews that they did, and reviews that their team received), and instructors (reviews that each time received, sorted by team; and reviews that each student did, sorted by student).

===Required Tasks===
The tasks involved as part of this requirements change are as follows:
# Compact the review display
#* Eliminate the blank lines between items within a single review. Instead vary the background color from line to line to improve readability
#* With a single click, there should be a way to hide all the reviews, reveal just the headings (as at present), or expand all the reviews
# At the top of each review, it should say
#* Who submitted the review. The instructor should see the user’s name and user-ID.
#* A student should see
#** “Reviewer #k”, where k is an integer between 1 and n, the number of reviews that have been submitted for this project
#** The version number of the review
#** The time the review was submitted
# There should be a tabbed view to switch between various review views
#* One tab has overall statistics (averages, min, max, as the present “normal” view)
#* One tab has the heat map (current “alternate” view)
#* One tab has a grid view, with no scores, but text comments in the grid squares, and then a “More” link to display the whole comment (which will require expanding the row of the grid)
#* Switching between reviews from Reviewer k and Reviewer j might also be done by clicking on different tabs. Or, it might be more convenient to keep the current score view, which lists the n reviews across the page. Then the student should be able to click on the reviewer number (the instructor would instead click on the reviewer name) and see the review done by that reviewer
# To make it easy to focus on the reviewer’s feedback, there should be a way to hide and/or gray the criteria (“questions”), so the responses stand out more clearly
# There needs to be a way to search all reviews (of a particular project, or by a particular individual) for a given text string. The user should be able to go from one instance of the text string to another by clicking down and up buttons

===Problem Statement===
In the current state, the score report for instructors and students are built differently though they display the same information using similar UI elements. The application has multiple views into the same information but the way in which those views are accessed, the code which populates them, and the layout of the screens differs unnecessarily between instructors and students and across the views themselves. This leads to redundant code in both the backend and frontend of the application. Furthermore, since the UI is not uniform between instructors and students, instructors may have difficulty assisting students in accessing their score information due to the differences which are present in the UI that leads to confusion.

Following are some of the issues with the current state UI which we seek to rectify.

====Scores Report====
[[File:Problem_Statement_Diagram_1A_-_Instructor_View_-_65.png]]

The scores report for students and instructors have very similar layouts despite being created by different controller methods and views. They both display graphs, reviews on team submissions, author feedback, and score metrics. The primary different between them is that the instructor view (shown above) displays information for all teams in a collapsible accordion widget format while the student view (shown below) display the information only for a single team. There are some further discontinuities between the two UIs. For example, the student cannot access the heatgrid view from within the scores report page. This view is only accessible from the assignment page for students. For instructors there are two ways to access the heatgrid view from a single page. The 'Alternate View' link is adjacent to the team name on the heading bar and there is also a link inexplicably placed beneath the 'Final Score' field.

[[File:Problem_Statement_Diagram_1B_-_Student_View_-_65.png]]

====Author Feedback====
Author feedback takes two different forms when being shown to instructors but only one form for students. Both students and instructors have access to the author feedback format shown on the left in the student view. This format is identical to the format of the review scores and is displayed on the scores report for both instructor and student. The format on the right is shown on the heatgrid view yet it is only available to instructors. The information conveyed by these two formats is nearly identical and not uniformly available to all consumers of this information.

[[File:Problem_Statement_Diagram_2_-_Author_Feedback_-_65.png]]

====Graphs and Charts====
The scores report view has a bar of graphs and charts at the top of the page for both students and instructors. Both views shown below use a donut chart and bar graphs though their method of display is not uniform. The instructor view has titles beneath each item but the student view does not. The 'Submitted work' and 'Author Feedback' titles shown, despite being beneath the bar graphs, are actually headings for the metrics which are displayed beneath the graphs. Also, the graphs contain two labels on the y-axis: the maximum score and the average score. The graphs are so compact that the values on the axis overlap and make them illegible.

[[File:Problem_Statement_Diagram_3_-_Squashed_Graphs_-_65.png]]

==Project Design==

===High Level Design===

====Design Overview====
The project requirements state that we need to create a standard UI for accessing and consuming review and score information. The emphasis will be on smart and purposeful code reuse as well as ease of navigation to access information. To achieve these results we will redesign the scores report to work for both instructors and students alike. There will be a single route, a single controller method, and a single view that is common t users of both role types. In some instances, such as with the graphs and charts, the data will be different enough to warrant separate methods to retrieve the values needed. In most instances, the data is identical and will be accessed identically.

We will create a standard hierarchy which works for both students (who only need to see a single team's scores) and instructors (who need to see all teams' scores). This hierarchy will be rendered within a page in the form of a set of tabbed panes which contain the contents. We will separate the information among four tabs.

# Reviews and scores
# Author Feedback
# Graphs and Charts
# Heatgrid

Putting these components on different tabs will allow us to de-clutter the UI. The instructor scores report UI has multiple ways to expand and collapse sections of information, links are placed in some unusual places, and the page can get so cluttered that it is difficult to distinguish one thing from another. This will be cleaned up by removing some links, removing the author feedback and the charts, and placing the reviews and scores into more discernible sections. The graphs and charts will be on their own tab so they can be larger and easier to read. Since they are not confined to a single bar of a fixed height new graphs and charts can be added. The heatgrid will no longer be coupled with the author feedback and there will be a standard author feedback view which encompasses all information needs. Each of these tabs will be rendered using their own partial.

To prevent the application from pulling data for tabs which the user will not view, AJAX calls will be used to access the data on demand without reloading the page. These calls can also be expanded to request data for individual sections. Routes will be created to controller methods specifically to pull the data for each tab so that calls can be made to them to generate the necessary data structures. These will be accessed when a user expands a group or switches tabs.

====Technologies Used====

{| class="wikitable"
|-
! Technology
! Technology Type
! Use(s)
|-
| Ruby
| Language
| Core development of the application's backend system
|-
| Rails
| Framework
| Implements MVC; CRUD support; Web application support
|-
| RSpec (rspec)
| Gem
| Enables TDD; supports testing DSL
|-
| JQuery (jquery.ui.tabs)
| Library
| Enables creation of tabbed Web interfaces
|-
| JQuery (jquery.ui.accordion)
| Library
| Enables creation of accordion widgets for Web interfaces
|-
| Sass (sass-rails)
| Gem
| Sass style sheet pre-processor engine
|-
| Cascading Style Sheets (CSS)
| Language
| Web page presentation description language
|-
| Sassy CSS (SCSS)
| Language
| Superset of CSS style sheet language
|-
| rails-ajax
| Gem
| Enable AJAX to refresh containers within views without reloading the page
|}

====Software Patterns====

'''Model-View-Controller (MVC)''' - MVC is a software architectural pattern which divides an application into three parts which separate the data representation from the interface through which users will access and operate on the data. The main components of this pattern are the:
* Model - The underlying logical structure of the application's data along with the accesses and operators on the data in the persistent storage medium.
* View - The user facing representation of the data along with the means for the user to request, operate on, or view the data.
* Controller - The intermediary layer between the Model and the View which accepts requests from the View, translates that to the Model, receives the Model's response and formats the response to the View.

'''Active Record''' - A software architectural pattern which wraps data from persistent storage, along with the method to operate on the data, in a class or object of a class to be used within an application. It uses the object-relation mapping (ORM) technique to create virtual database objects.

===Low Level Design===

====Screen Mockups====

'''New Scores Report With Multiple Teams and Collapsed Reviews'''

[[File:Expanded_Teams_With_Collapsed_Tabs_-_45.png]]

'''New Scores Report With Multiple Teams and Expanded Reviews'''

[[File:Expanded_Teams_With_Expanded_Tabs_-_85.png]]

==Test Plan==
In order to test the functionality of our updates, we will focus on reusing the existing test cases which validate the current views for the score report and the reviews report. Since the goal is to make the code which generates these views common, the tests will include generation of pages from a student login and instructor login to verify that the common elements are present. This will also ensure that the underlying code which is used to generate the two views works as expected. For the sections of the views which differ, such as the displaying of reviewer name, we will write independent test that ensure the correct name is listed based on the logged in user type.

Additionally to explicitly testing our updates, we will update the other tests which rely on the contents of the pages in order to invoke various functionality. An example of this will be the addition of the tabbed views. The existing tests will be updated in order to account for the transition to the appropriate tab before selecting links as appropriate.

{| class="wikitable"
! colspan="2" | Test Case 1
|-
! Test Type
| Functional
|-
! Scenario
| Test to see if modifications to the display_as_html function in response.rb order to hide the “feedback review” button is correct for a student
|-
! Pre-Conditions
|
Make sure student to test with has the following:
#Has one course assigned
#Has one assigned as part of that course
#Has more than one review for that assignment
|-
! Description
|
#Login to the site as a student
#Click on "Assignments" on the top menu
#Select an assignment from the list
#On the "Submit or Review work for Expertiza" screen, click on "Your scores”
#On the "Summary Report for assignment" screen, verify that the "Give feedback for Review 1" button is not present
|-
| colspan="2" |  
|-
! colspan="2" | Test Case 2
|-
! Test Type
| Functional
|-
! Scenario
| Test to see if modifications to the display_as_html function in response.rb order to show the “feedback review” button is correct for a student
|-
! Pre-Conditions
|
Make sure student to test with has the following:
#Has one course assigned
#Has one assigned as part of that course
#Has more than one review for that assignment
|-
! Description
|
#Login to the site as a student
#Click on "Assignments" on the top menu
#Select an assignment from the list
#On the "Submit or Review work for Expertiza" screen, click on "Your scores”
#On the “Summary Report for assignment” screen, select the “Show Review” button
#On the "Summary Report for assignment" screen, verify that the "Give feedback for Review 1" button is present
|-
| colspan="2" |  
|-
! colspan="2" | Test Case 3
|-
! Test Type
| Functional
|-
! Scenario
| Test to see if modifications to the display_as_html function in response.rb order to hide the “feedback review” button is correct for an instructor
|-
! Pre-Conditions
|
Make sure student to test with has the following:
#At least one assignment exists
#Has more than one review for that assignment
|-
! Description
|
#Login to the site as an instructor
#Click on "Manage" on the top menu
#Click on “Assignments”
#Select an assignment from the list
#Click on "View Scores”
#On the "Summary Report for assignment" screen, verify that the "Give feedback for Review 1" button is not present
|-
| colspan="2" |  
! colspan="2" | Test Case 4
|-
! Test Type
| Functional
|-
! Scenario
| Test to see if modifications to the display_as_html function in response.rb order to show the “feedback review” button is correct for an instructor
|-
! Pre-Conditions
|
Make sure student to test with has the following:
#At least one assignment exists
#Has more than one review for that assignment
|-
! Description
|
#Login to the site as an instructor
#Click on "Manage" on the top menu
#Click on “Assignments”
#Select an assignment from the list
#Click on "View Scores”
#On the “Summary Report for assignment” screen, select the “Show Review” button
#On the "Summary Report for assignment" screen, verify that the "Give feedback for Review 1" button is present
|-
| colspan="2" |  

E1735. UI changes for review and score reports

2017-04-08T02:58:08Z

Remcelfr: /* Test Plan */

2014-02-26T15:55:31Z

Remcelfr:

CSC/ECE 506 Spring 2014/5a rm

2014-02-26T15:55:07Z

Remcelfr:

= Chapter 5a CSC/ECE 506 Spring 2014 / Other linked data structures =

Original wiki : http://wiki.expertiza.ncsu.edu/index.php/CSC/ECE_506_Spring_2013/5a_ks

= Overview =

Linked Data Structures (LDS) consists of different types of data structures such as [http://en.wikipedia.org/wiki/Linked_list linked lists], [http://en.wikibooks.org/wiki/Data_Structures/Trees trees], [http://en.wikipedia.org/wiki/Hash_table hash tables] and [http://en.wikibooks.org/wiki/Data_Structures/Graphs graphs]. Although each structure is diversed, LDS traversal shares a common characteristic in reading a node and discovering the other nodes it points to. Hence, this often introduces loop carried dependence. Chapter 5 of Solihin, discusses various algorithms on parallelizing LDS using a simple linked list. In this wiki, we attempt to cover other LDS such as trees, hashes and graphs, and how the parallelization algorithms discussed can be applied to these structures. This wiki explores concurrency problems related to each type and possible solutions for parallelizing them.

= Introduction to Linked-List Parallel Programming =

One component that tends to link together various data structures is their reliance at some level on an internal pointer-based linked list. For example, hash tables have linked lists to support chained links to a given bucket in order to resolve collisions, trees have linked lists with left and right tree node paths, and graphs have linked lists to determine shortest path algorithms.

But what mechanism allows us to generate parallel algorithms for these structures?

For an array processing algorithm, a common technique used at the processor level is the copy-scan technique. This technique involves copying rows of data from one processor to another in a log(n) fashion until all processors have their own copy of that row. From there, you could perform a reduction technique to generate a sum of all the data, all while working in a parallel fashion. Take the following grid:[[#References|[1]]]

The basic process for copy-scan would be to:
Step 1) Copy the row 1 array to row 2.
Step 2) Copy the row 1 array to row 3, row 2 to row 4, etc on the next run.
Step 3) Continue in this manner until all rows have been copied in a log(n) fashion.
Step 4) Perform the parallel operations to generate the desired result (reduction for sum, etc.).

[[File:CopyScan.gif]]

But how does this same process work in the linked list world?

With linked lists, there is a concept called pointer doubling, which works in a very similar manner to copy-scan.[[#References|[1]]]

Step 1) Each processor will make a copy of the pointer it holds to its neighbor.
Step 2) Next, each processor will make a pointer to the processor 2 steps away.
Step 3) This continues in logarithmic fashion until each processor has a pointer to the end of the chain.
Step 4) Perform the parallel operations to generate the desired result.

One of the uses for pointer doubling is to perform partial sums of a linked list. The way that this is accomplished is by adding the value held by the node with the value stored in the node it is pointing to. This is repeated until all pointers have reached the end of the list. The result is a linked list which contains the sum of the node and all preceding nodes. Below shows and example of this operation in action.

[[File:PartialSums1.png]]

[[File:PartialSums2.png]]

[[File:PartialSums3.png]]

[[File:PartialSums4.png]]

However, with linked list programming, similar to array-based programming, it becomes imperative to have some sort of locking mechanism or other parallel technique for [http://en.wikipedia.org/wiki/Critical_section critical sections] in order to avoid [http://en.wikipedia.org/wiki/Race_condition race conditions]. To make sure the results are correct, it is important that operations can be serialized appropriately and that data remains current and synchronized.

In this chapter, we will explore 3 linked-list based data structures and the parallelization opportunities as well as the concurrency issues they present: hash tables, trees, and graphs.

== Trees ==

=== Tree Intro ===

A tree data structure [[#References|[2]]] contains a set of ordered nodes with one parent node followed by zero or more child nodes. Typically this tree structure is used with searching or sorting algorithms to achieve log(n) efficiencies. Assuming you have a balanced tree, or a relatively equal set of nodes under each branching structure of the tree, and assuming a proper ordering structure, searches/inserts/deletes should occur far more quickly than having to traverse an entire list.

=== Opportunities for Parallelization ===

One potential slowdown in a tree data structure could occur during the traversal process. Even though search/update/insert can occur in a logarithmic fashion, traversal operations such as in-order, pre-order, post-order traversals can still require a full sequence of the list to generate all output. This gives an opportunity to generate parallel code by having various portions of the traversal occur on different processors.

=== Serial Code Example ===

Below is a code[[#References|[8]]] for serial tree traversal algorithms
with behavior as the figure below shows:

[[File: tree.PNG]]

procedure Tree_Traversal is
type Node;
type Node_Access is access Node;
type Node is record
Left : Node_Access := null;
Right : Node_Access := null;
Data : Integer;
end record;

procedure Destroy_Tree(N : in out Node_Access) is
procedure free is new Ada.Unchecked_Deallocation(Node, Node_Access);
begin
if N.Left /= null then
Destroy_Tree(N.Left);
end if;
if N.Right /= null then
Destroy_Tree(N.Right);
end if;
Free(N);
end Destroy_Tree;

function Tree(Value : Integer; Left : Node_Access; Right : Node_Access) return Node_Access is
Temp : Node_Access := new Node;
begin
Temp.Data := Value;
Temp.Left := Left;
Temp.Right := Right;
return Temp;
end Tree;

procedure Preorder(N : Node_Access) is
begin
Put(Integer'Image(N.Data));
if N.Left /= null then
Preorder(N.Left);
end if;
if N.Right /= null then
Preorder(N.Right);
end if;
end Preorder;

procedure Inorder(N : Node_Access) is
begin
if N.Left /= null then
Inorder(N.Left);
end if;
Put(Integer'Image(N.Data));
if N.Right /= null then
Inorder(N.Right);
end if;
end Inorder;

procedure Postorder(N : Node_Access) is
begin
if N.Left /= null then
Postorder(N.Left);
end if;
if N.Right /= null then
Postorder(N.Right);
end if;
Put(Integer'Image(N.Data));
end Postorder;

procedure Levelorder(N : Node_Access) is
package Queues is new Ada.Containers.Doubly_Linked_Lists(Node_Access);
use Queues;
Node_Queue : List;
Next : Node_Access;
begin
Node_Queue.Append(N);
while not Is_Empty(Node_Queue) loop
Next := First_Element(Node_Queue);
Delete_First(Node_Queue);
Put(Integer'Image(Next.Data));
if Next.Left /= null then
Node_Queue.Append(Next.Left);
end if;
if Next.Right /= null then
Node_Queue.Append(Next.Right);
end if;
end loop;
end Levelorder;

N : Node_Access;
begin
N := Tree(1,
Tree(2,
Tree(4,
Tree(7, null, null),
null),
Tree(5, null, null)),
Tree(3,
Tree(6,
Tree(8, null, null),
Tree(9, null, null)),
null));

Put("preorder: ");
Preorder(N);
New_Line;
Put("inorder: ");
Inorder(N);
New_Line;
Put("postorder: ");
Postorder(N);
New_Line;
Put("level order: ");
Levelorder(N);
New_Line;
Destroy_Tree(N);
end Tree_traversal;

=== Parallel Solution ===
[[#References|[21]]]
In many ways, a tree is the perfect candidate for parallelism. In a tree, each
node/subtree is independent. As a result, we can split up a large tree into 2, 4, 8, or
more subtrees and hold subtree on each processor. Then, the only duplicated data
that must be kept on all processors is the tiny tip of the tree that is the parent of all
of the individual subtrees. Mathematically speaking, for a tree divided among n
processors (where n is a power of two), the processors only need to hold n – 1 nodes
in common – no matter how big the tree itself is. This is shown in the figure below. Since we are using 4 processors, we will only need 3 nodes in common. This is because one node is capable of having two branches. If the size of the tree was increased and the number of processors was also increased, the number of shared nodes would also increase to support the increased number of sub-trees.

The fact that trees are comprised of independent sub-trees makes parallelizing them
very easy. Properly done, the portion of these traversals that is parallelizable grows
at 2n for an n-generation tree, while the processors only need to synchronize once, at
the end, so parallelizable portion approaches 100% for large trees (but keep in mind [http://en.wikipedia.org/wiki/Amdahl's_law Amdahl’s Law],
footnote 1). The basic steps for parallelizing these traversals are as follows:

1. Perform the traversal on the parent part of the tree.
2. Whenever you get to a node that is only present on one processor, ask that processor to execute the appropriate C algorithm detailed above.
3. The processor will return its result that can be used exactly as if it was a serial processor.

[[File:parallel_tree.png]][[#References|[18]]]

A [http://www.cs.bu.edu/teaching/c/tree/breadth-first/ Breadth-First traversal] is somewhat more complicated to implement as a
parallel system because at each level, it must access nodes from all of the parallel
processors. Theoretically, a Breadth-First traversal can achieve the same 100%
code parallelization of Pre-, In-, and Post-Order traversals. However, the amount of processor to
processor data transmission adds in a greater potential for delays, thus slowing
down the algorithm. Nevertheless, as the size of the tree increases the size of the
generations grows at the rate of 2n while the number of synchronizations grows at a
rate of n for an n-generation tree, so the parallelizable portion of these traversals
also approaches 100%. The basic steps for parallelizing this traversal are as
follows:

1. Perform the traversal on the parent part of the tree.
2. Whenever you get to a node that is only present on one processor, ask that processor to execute the Breadth-First C algorithm detailed above,
but wait after it finishes one generation.
3. Combine all the one-generation results from the different processors in the correct order.
4. Allow each processor to execute the next generation of the Breadth-First C algorithm detailed above, and then wait again.
5. Repeat Steps 3 and 4 until there are no nodes remaining
[[#References|[18]]]

Here, since each processor is assigned an independent sub-tree, elaborate locks are not required.

An example of a parallel Breadth-First tree traversal is shown below.

[[File:ExampleTree.png]]

Algorithm GEN-COMP-NEXT for Parallel Tree Traversal:
for all Pi, 1<=i<=n, do
parallel begin
Step 1: Processor Pi builds the jth field of i's parent node if i is the jth child of its parent.
The jth field (if it is not the last field) is stored in the ith index of array SUPERNODE.
Step 2: Processor Pi builds node i's last fiend whose array index is (n+1)
parallel end

Below is the algorithm to perform a Breadth-First tree traversal in parallel wheer bfrank is the output parameter, array[1..n] of integer; level is the input parameter, array[1..n] of integer; and preorder list is an input parameter, array[1..n] of integer.

Algorith BF-TRAVERSAL (bfank, level, preorder-list)
Step 1. Divide the preorder-list into p blocks. Each processor builds partial lists from the nodes in the block. The header and the taller arrays for the lists built by processor i are denoted by hd[*,i] and tl[*,i], respectively.
for all Pi, 1<=i<=p do
parbegin
Pi works on nodes pre-order-list[k], where (i-1)*(n/p) <= k < (i*n/p)
Pi initializes list[k] to zreo /* the successor of k-th input in a partial list */
/* Phase 1. Pi initializes entries in hd[*,i] and tl[*,i] that are used and entries in hdflag */
hd[level[preorder-list[k]], i] := 0; tl[level[preorder-list[k]], i] := 0; hdflag[k] := 0;
/* Phase 2. Build partial lists */
Pi adds each of the n/p nodes to the partial list for the level of that node and updates hd[*,i], tl[*, i], and list [*] accordingly.
parend;
Step 2. Link up partial lists.
/* Phase 1. Initialize header and tailer for the global lists */
for all Pi, 1 <= i <= p, do
initialize head[k] and tail[k] to zero, for (i-1)*n/p <= k < (i*n/p)
P1 sets head[n+1] and tail[n+1] to zero;
/* Phase 2. Link partial lists to form a list for each level */
for each of the p blocks do
for all Pi, 1 <= i <= p, do /* all processors work on the same block */
parbegin
for i := 1 to (n/p^2) do
begin
Pi is given at most a node mi in each iteration.
if hdflag[mi] = 1 /* The first element in its partial list */
then
if the global list for the level of node mi is empty
then let head[level[mi]] and tail[level[mi]] point to mi
else list[tail[level[mi]]] := mi and update tail[level[mi]] to be the tail of the partial list for mi.
end;
parend;
Step 3. Create a linked list to implement the NEXT function
for all Pi, 1 <= i <= p, do
parbegin
for k := (i-1)*(n/p)+1 to (i*n/p) do
if(head[k] != 0 and head[k+1] != 0) then list[tail[k]] := head[k+1];
parend;
Step 4. Obtain ranking
LINKED-LIST-RANKING(list, tmp-rank, n);
Step 5. Output the result
for all Pi, 1 <= i <= p, do
parbegin
for k := (i-1)*(n/p)+1 to (i*n/p) do bfrank[preorder-list[k]] := tmp-rank[k];
parend;

To obtain the required tree-traversals, the following rules are operated on the linked list produced by algorithm GEN-COMP-NEXT:
pre-order traversal: select the first copy of each node;
post-order traversal: select the last copy of each node;
in-order traversal: delete the first copy of each node if it is not a leaf and delete the last copy of each node if it has more than one child.
This linked list can be locked while editing as per the LDS chapter in Solihin book. Either a Global lock approach, Fine Grained approach or [http://en.wikipedia.org/wiki/Readers%E2%80%93writer_lock Read-Write Locks] can be used.
In this fashion we have broken up the linked list of the tree into successive parts and imposed a divide-and-conquer technique to complete the traversal.

== Hash Tables ==
'''Hash Table Intro '''

Hash tables[[#References|[4]]] are very efficient data structures often used in searching algorithms for fast lookup operations. They are used extensively in data processing as in involves a vast amount of data through the hash table using as few indirection's in the storage structure as possible.

A single hash table level look can easily become a bottleneck, thus several method were developed to overcome this difficulty. Hash tables contain a series of "buckets" that function like indexes into an array, each of which can be accessed directly using their key value. The bucket for which a piece of data will be placed is determine by a special hashing function.

The major advantage of a hash table is that lookup times are essentially a constant value, much like an array with a known index. With a proper hashing function in place, it should be fairly rare that any 2 keys would generate the same value.

In the case that 2 keys do map to the same position, there is a conflict that must be dealt with in some fashion to obtain the correct value. One way that is relevant to linked list structures is to have a chained hash table in which a linked list is created with all values that have been placed in that particular bucket. The developer would have to not only take into account the proper bucket for the data being searched for, but also must considered the chained linked list. [[#References|[7]]]

There are several parallel implementations of hash tables available that use lock based synchronization. Larson et al. use two lock levels, there is one global table level lock, and there is one separate lightweight lock (a flag) for each bucket. The high level lock is just used for setting the bucket level flags and released right afterwards. This ensures a fine grained mutual exclusion (concurrent operations on bucket level), but needs only one real lock for the implementation.

A scalable hash table for shared memory multi-processor (SMP) supports very high rates of concurrent operations (e.g., insert, delete,
and lookup), while simultaneously reducing cache misses. The SMP system has a memory subsystem and a processor subsystem interconnected
via a bus structure.

The hash table is stored in the memory subsystem to facilitate access to data items. The hash table is segmented into multiple buckets,
with each bucket containing a reference to a linked list of bucket nodes that hold references to data items with keys that hash to a common value. Individual bucket nodes contain multiple signature-pointer pairs that reference corresponding data items.
Each signature-pointer pair has a hash signature computed from a key of the data item and a pointer to the data item. The first bucket
node in the linked list for each of the buckets is stored in the hash table.

To enable multithread access, while serializing operation of the table, the SMP system utilizes two levels of locks: a table lock and
multiple bucket locks. The table lock allows access by a single processing thread to the table while blocking access for other processing
threads. The table lock is held just long enough for the thread to acquire the bucket lock of a particular bucket node. Once the table lock
is released, another thread can access the hash table and any one of the other buckets.

[[File:315px-Hash table 3 1 1 0 1 0 0 SP.svg.png]]

=== Opportunities for Parallelization ===

Hash tables can be very well suited to parallel applications. For example, system code responsible for caching between multiple processors could itself be an ideal opportunity for a shared hashmap. Each processor sharing one common cache would be able to access the relevant information all in one location.

This would, however, involve a good bit of synchronization, as each processor would need to wait in case a lock was being placed on a specific bucket in the cache hashmap. Unfortunately, traditional locking would be a bad solution to this problem as processors need to run very quickly. Having to wait for locks would destroy the application processing time. The need for a non-locking solution is critical to performance.

In Java, the standard class utilized for hashing is the HashMap[[#References|[17]]] class. This class has a fundamental weakness though in that the entire map requires synchronization prior to each access. This causes a lot of contention and many bottlenecks on a parallel machine.

Below, I will present a Java-based solution to this problem by using a ConcurrentHashMap class. This class only requires a portion of the map to be locked and reads can generally occur with no locking whatsoever.

=== HashMap Code with Locking ===

''' Simple synchronized example to increment a counter.'''[[#References|[9]]]
private Map<String,Integer> queryCounts = new HashMap<String,Integer>(1000);
private '''synchronized''' void incrementCount(String q) {
Integer cnt = queryCounts.get(q);
if (cnt == null) {
queryCounts.put(q, 1);
} else {
queryCounts.put(q, cnt + 1);
}
}

The above code was written using an ordinary HashMap data structure. Notice that we use the synchronized keyword here to signify that only one thread can enter this function at any one point in time. With a really large number of threads, however, waiting to enter the synchronized operation could be a major bottleneck.

''' Iterator example for synchronized HashMap.'''

Map m = Collections.synchronizedMap(new HashMap());
Set s = m.keySet(); // set of keys in hashmap
synchronized(m) { // synchronizing on map
Iterator i = s.iterator(); // Must be in synchronized block
while (i.hasNext())
foo(i.next());
}

In the above example, we show how an iterator could be used to traverse over a map. In this case, we would need to utilize the synchronizedMap function available in the Collections interface. Also, as you may notice, once the iterator code begins we must actually synchronize on the entire map in order to iterate through the results. But what if several processors wish to iterate through at the same time?

=== Parallel Code Solution ===

The key issue in a hash table in a parallel environment is to make sure any update/insert/delete sequences have been completed properly prior to attempting subsequent operations to make sure the data has been synched appropriately. However, since access speed is such a critical component of the design of a hash table, it is essential to try and avoid using too many locks for performing synchronization. Fortunately, a number of lock-free hash designs have been implemented to avoid this bottleneck.

One such example in Java is the ConcurrentHashMap[[#References|[9]]], which acts as a synchronized version of the [http://docs.oracle.com/javase/6/docs/api/java/util/HashMap.html HashMap]. With this structure, there is full concurrency of retrievals and adjustable expected concurrency for updates. There is, however, no locking in this data structure and retrievals will typically run in parallel along with updates/deletes. Retrievals, however, will receive all most recently completed transactions even if it cannot get the values that haven't finished being updated. This both allows for efficiency and greater concurrency.

'''Parallel Counter Increment Alternative:'''

private ConcurrentMap<String,Integer> queryCounts =
new ConcurrentHashMap<String,Integer>(1000);
private void incrementCount(String q) {
Integer oldVal, newVal;
do {
oldVal = queryCounts.get(q);
newVal = (oldVal == null) ? 1 : (oldVal + 1);
} while (!queryCounts.replace(q, oldVal, newVal));
}

The above code snippet represents an alternative to the serial option presented in the previous section, while also avoiding much of the locking that takes place using the synchronized functions or synchronized blocks. With ConcurrentHashMap, however, notice that we must implement some new code in order to handle the fact that a variety of inserts/updates could be running at the same time. The replace() function here acts much like a compare-and-set operation typically used with concurrent code. Basically, the value would be changed only if not equal to the previously mapped value. This is much more efficient that locking the entire function as we often do not expect unequal values.

'''Parallel Traversal Alternative:'''

Map m = new ConcurrentHashMap();
Set s = m.keySet(); // set of keys in hashmap
Iterator i = s.iterator(); // Must be in synchronized block
while (i.hasNext())
foo(i.next());

In the case of a traversal, recall that ConcurrentHashMaps require to locking on read operations. Thus we can actually remove the synchronized condition here and iterate in a normal fashion.

== Graphs ==
=== Graph Intro ===

A graph data structure[[#References|[10]]] is another type of linked-list structure that focuses on data relationships and the most efficient ways to traverse from one node to another. For example, in a networking application, one network node may have connections to a variety of other network nodes. These nodes then also link to a variety of other nodes in the network. Using this connection of nodes, it would be possible to then find a path from one specific node to another in the chain. This could be accomplished by having each node contain a linked list of pointers to all other reachable nodes.

[[File:250px-6n-graf.svg.png]]

=== Opportunities for Parallelization ===

Graphs[[#References|[10]]] consist of a finite set of ordered pairs called edges or arcs, of certain entities called nodes or vertices. From one given vertex, one would typically want to order the different paths from one vertex to another using its list of edges or, more than likely, would be interested in the fastest means of getting from one of these vertexes to some sort of destination vertex.

Graph nodes typically will keep their list of edges in a linked list. Also, when attempting to create a shortest path algorithm on the fly, the graph will typically use a combination of a linked list to represent the path as it's being built, along with a queue that is used for each step of that process. Synchronizing all of these can be a major challenge.

Much like the hash table, graphs cannot afford to be slow and must often generate results in a very efficient manner. Having to lock on each list of edges or locking on a shortest path list would really be a major obstacle.

Certainly though, the need for parallel processing becomes critical when you consider, for example, that social networking has become such a major proponent of graph algorithms. Facebook now has roughly a billion users[[#References|[15]]] and each user has series of friend links that must be analyzed and examined. This list just keeps growing and growing.

One of the most significant opportunities for a parallel algorithm with a graph data structure is with the traversal algorithms. We can use Breadth-First search[[#References|[16]]] as an example of this, starting from an initial node and expanding outwards until reaching the destination node.

=== Breadth First Search - Serial Version ===

The following shows a sample of a bread first algorithm which traverses from the city of Frankfurt to Augsburg and Stuttgart Germany. In does so, the graph begins at a root node (Frankfurt) and expands outwardly to all connected nodes on each step. From there, each of those nodes proceeds to expand the search outwards until all nodes have been covered.

[[File:GermanyBFS.png]][[#References|[13]]]

The following code snippet implements a BFS search function. This function utilized coloring schemes and marks to denote that a node has been visited. It begins with an initial vertex in a queue and expands outward to all its successors until no further elements remain unmarked.[[#References|[12]]]

public void search(Graph g)
{
g.paint(Color.white); // paint all the graph vertices with white
g.mark(false); // unmark the whole graph
refresh(null); // and redraw it
Vertex r = g.root(); // the root is painted grey
g.paint(r, Color.gray); refresh(g.box(r));
java.util.Vector queue = new java.util.Vector();
queue.addElement(r); // and put in a queue
while(!queue.isEmpty())
{
Vertex u = (Vertex) queue.firstElement();
queue.removeElement(u); // extract a vertex from the queue
g.mark(u, true); refresh(g.box(u));
int dp = g.degreePlus(u);
for(int i = 0; i < dp; i++) // look at its successors
{
Vertex v = g.ithSucc(i, u);
if(Color.white == g.color(v))
{
queue.addElement(v);
g.paint(v, Color.gray); refresh(g.box(v));
}
}
g.paint(u, Color.black); refresh(g.box(u));
g.mark(u, false); refresh(g.box(u));
}
}

=== Parallel Solution ===

But could we introduce parallel mechanisms into this Breadth First search? The most logical and effective way, instead of utilizing locks and synchronized regions, is to use data parallel techniques during the traversal. This can be accomplished by having each node of a given breadth search step be sent to a separate processor. So, using the above example, instead of having Frankfurt->Mannheim followed by Frankfurt->Wurzburg followed by Frankfurt->Bassel on the same processor, Frankfurt could split out all 3 searches in a parallel fashion onto 3 different processors. Then, possible some cleanup code would be left at the end to visit any remaining untouched nodes. In a network routing applications, being able to split up the search for each IP address code would make searched significantly faster that allowing one processor to be a bottleneck.

Using locking pseudocode, you might have an algorithm similar to this:

for all vertices u at level d in parallel do
for all adjacencies v of u in parallel do
dv = D[v];
if(dv < 0) // v is visited for the first time
vis = fetch_and_add(&Visited[v], 1); '''LOCK'''
if(vis == 0) // v is added to a stack only once
D[v] = d+1;
pS[count++] = v; // Add v to local thread stack
fetch_and_add(&sigma[v], sigma[u]); '''LOCK'''
fetch_and_add(&Pcount[v], 1); // Add u to predecessor list of v '''LOCK'''
if(dv == d + 1)
fetch_and_add(&sigma[v], sigma[u]); '''LOCK'''
fetch_and_add(&Pcount[v], 1); // Add u to predecessor list of v '''LOCK'''

A much better parallel algorithm is represented in the following pseudocode. Notice that each of the vertices is sent to a separate processor and send/receive operations will eventually sync up the path information.

[[File:Parallel-code.PNG]][[#References|[14]]]

The following graph also shows how now each of the regional sets of vertices being search can be added to the path in a parallel fashion.

[[File:Parallel-graph.PNG]][[#References|[11]]]

Every set of vertices in the same distance from the source is assigned to a processor. This set of vertices is called a regional set of vertices. The goal is to find the shortest path connecting each region.

= Quiz =

1. Describe the copy-scan technique.

2. Describe the pointer doubling technique.

3. Which concurrency issues are of the most concern in a tree data structure?

4. What is the alternative to using a copy-scan technique in pointer-based programming?

5. Which concurrency issues are of the most concern with hash table data structures?

6. Which concurrency issues are of the most concern with graph data structures?

7. Why would you not want locking mechanisms in hash tables?

8. What is the nature of the linked list in a tree structure?

9. Describe a parallel alternative in the tree data structure.

10. Describe a parallel alternative in a graph data structure.

= References =

#http://people.engr.ncsu.edu/efg/506/s01/lectures/notes/lec8.html
#http://en.wikipedia.org/wiki/Tree_%28data_structure%29
#http://oreilly.com/catalog/masteralgoc/chapter/ch08.pdf
#http://www.devjavasoft.org/code/classhashtable.html
#http://osr600doc.sco.com/en/SDK_c++/_Intro_graph.html
#http://web.eecs.utk.edu/~berry/cs302s02/src/code/Chap14/Graph.java
#http://en.wikipedia.org/wiki/File:Hash_table_3_1_1_0_1_0_0_SP.svg
#http://rosettacode.org/wiki/Talk:Tree_traversal
#http://www.javamex.com/tutorials/synchronization_concurrency_8_hashmap.shtml
#http://en.wikipedia.org/wiki/Graph_%28abstract_data_type%29
#http://www.cc.gatech.edu/~bader/papers/PPoPP12/PPoPP-2012-part2.pdf
#http://renaud.waldura.com/portfolio/graph-algorithms/classes/graph/BFSearch.java
#http://en.wikipedia.org/w/index.php?title=File%3AGermanyBFS.svg
#http://sc05.supercomputing.org/schedule/pdf/pap346.pdf
#http://www.facebook.com/press/info.php?statistics
#http://en.wikipedia.org/wiki/Breadth-first_search
#http://code.wikia.com/wiki/Hashmap
#http://www.shodor.org/petascale/materials/UPModules/Binary_Tree_Traversal
#http://en.wikipedia.org/wiki/Readers%E2%80%93writer_lock
#http://dl.acm.org/citation.cfm?id=320078
#http://en.wikipedia.org/wiki/Tree_traversal
P.-A. Larson, M. R. Krishnan,and G. V. Reilly, “Scaleable hash table for
shared-memory multiprocessor system,” US Patent number: 6578131,
2003
http://ww2.cs.mu.oz.au/~pjs/papers/paralleldp.pdf

CSC/ECE 506 Spring 2014/5a rm

2014-02-26T05:28:31Z

Remcelfr:

= Chapter 5a CSC/ECE 506 Spring 2014 / Other linked data structures =

Original wiki : http://wiki.expertiza.ncsu.edu/index.php/CSC/ECE_506_Spring_2013/5a_ks

= Overview =

Linked Data Structures (LDS) consists of different types of data structures such as [http://en.wikipedia.org/wiki/Linked_list linked lists], [http://en.wikibooks.org/wiki/Data_Structures/Trees trees], [http://en.wikipedia.org/wiki/Hash_table hash tables] and [http://en.wikibooks.org/wiki/Data_Structures/Graphs graphs]. Although each structure is diversed, LDS traversal shares a common characteristic in reading a node and discovering the other nodes it points to. Hence, this often introduces loop carried dependence. Chapter 5 of Solihin, discusses various algorithms on parallelizing LDS using a simple linked list. In this wiki, we attempt to cover other LDS such as trees, hashes and graphs, and how the parallelization algorithms discussed can be applied to these structures. This wiki explores concurrency problems related to each type and possible solutions for parallelizing them.

= Introduction to Linked-List Parallel Programming =

One component that tends to link together various data structures is their reliance at some level on an internal pointer-based linked list. For example, hash tables have linked lists to support chained links to a given bucket in order to resolve collisions, trees have linked lists with left and right tree node paths, and graphs have linked lists to determine shortest path algorithms.

But what mechanism allows us to generate parallel algorithms for these structures?

For an array processing algorithm, a common technique used at the processor level is the copy-scan technique. This technique involves copying rows of data from one processor to another in a log(n) fashion until all processors have their own copy of that row. From there, you could perform a reduction technique to generate a sum of all the data, all while working in a parallel fashion. Take the following grid:[[#References|[1]]]

The basic process for copy-scan would be to:
Step 1) Copy the row 1 array to row 2.
Step 2) Copy the row 1 array to row 3, row 2 to row 4, etc on the next run.
Step 3) Continue in this manner until all rows have been copied in a log(n) fashion.
Step 4) Perform the parallel operations to generate the desired result (reduction for sum, etc.).

[[File:CopyScan.gif]]

But how does this same process work in the linked list world?

With linked lists, there is a concept called pointer doubling, which works in a very similar manner to copy-scan.[[#References|[1]]]

Step 1) Each processor will make a copy of the pointer it holds to its neighbor.
Step 2) Next, each processor will make a pointer to the processor 2 steps away.
Step 3) This continues in logarithmic fashion until each processor has a pointer to the end of the chain.
Step 4) Perform the parallel operations to generate the desired result.

One of the uses for pointer doubling is to perform partial sums of a linked list. The way that this is accomplished is by adding the value held by the node with the value stored in the node it is pointing to. This is repeated until all pointers have reached the end of the list. The result is a linked list which contains the sum of the node and all preceding nodes. Below shows and example of this operation in action.

[[File:PartialSums1.png]]

[[File:PartialSums2.png]]

[[File:PartialSums3.png]]

[[File:PartialSums4.png]]

However, with linked list programming, similar to array-based programming, it becomes imperative to have some sort of locking mechanism or other parallel technique for [http://en.wikipedia.org/wiki/Critical_section critical sections] in order to avoid [http://en.wikipedia.org/wiki/Race_condition race conditions]. To make sure the results are correct, it is important that operations can be serialized appropriately and that data remains current and synchronized.

In this chapter, we will explore 3 linked-list based data structures and the parallelization opportunities as well as the concurrency issues they present: hash tables, trees, and graphs.

== Trees ==

=== Tree Intro ===

A tree data structure [[#References|[2]]] contains a set of ordered nodes with one parent node followed by zero or more child nodes. Typically this tree structure is used with searching or sorting algorithms to achieve log(n) efficiencies. Assuming you have a balanced tree, or a relatively equal set of nodes under each branching structure of the tree, and assuming a proper ordering structure, searches/inserts/deletes should occur far more quickly than having to traverse an entire list.

=== Opportunities for Parallelization ===

One potential slowdown in a tree data structure could occur during the traversal process. Even though search/update/insert can occur in a logarithmic fashion, traversal operations such as in-order, pre-order, post-order traversals can still require a full sequence of the list to generate all output. This gives an opportunity to generate parallel code by having various portions of the traversal occur on different processors.

=== Serial Code Example ===

Below is a code[[#References|[8]]] for serial tree traversal algorithms
with behavior as the figure below shows:

[[File: tree.PNG]]

procedure Tree_Traversal is
type Node;
type Node_Access is access Node;
type Node is record
Left : Node_Access := null;
Right : Node_Access := null;
Data : Integer;
end record;

procedure Destroy_Tree(N : in out Node_Access) is
procedure free is new Ada.Unchecked_Deallocation(Node, Node_Access);
begin
if N.Left /= null then
Destroy_Tree(N.Left);
end if;
if N.Right /= null then
Destroy_Tree(N.Right);
end if;
Free(N);
end Destroy_Tree;

function Tree(Value : Integer; Left : Node_Access; Right : Node_Access) return Node_Access is
Temp : Node_Access := new Node;
begin
Temp.Data := Value;
Temp.Left := Left;
Temp.Right := Right;
return Temp;
end Tree;

procedure Preorder(N : Node_Access) is
begin
Put(Integer'Image(N.Data));
if N.Left /= null then
Preorder(N.Left);
end if;
if N.Right /= null then
Preorder(N.Right);
end if;
end Preorder;

procedure Inorder(N : Node_Access) is
begin
if N.Left /= null then
Inorder(N.Left);
end if;
Put(Integer'Image(N.Data));
if N.Right /= null then
Inorder(N.Right);
end if;
end Inorder;

procedure Postorder(N : Node_Access) is
begin
if N.Left /= null then
Postorder(N.Left);
end if;
if N.Right /= null then
Postorder(N.Right);
end if;
Put(Integer'Image(N.Data));
end Postorder;

procedure Levelorder(N : Node_Access) is
package Queues is new Ada.Containers.Doubly_Linked_Lists(Node_Access);
use Queues;
Node_Queue : List;
Next : Node_Access;
begin
Node_Queue.Append(N);
while not Is_Empty(Node_Queue) loop
Next := First_Element(Node_Queue);
Delete_First(Node_Queue);
Put(Integer'Image(Next.Data));
if Next.Left /= null then
Node_Queue.Append(Next.Left);
end if;
if Next.Right /= null then
Node_Queue.Append(Next.Right);
end if;
end loop;
end Levelorder;

N : Node_Access;
begin
N := Tree(1,
Tree(2,
Tree(4,
Tree(7, null, null),
null),
Tree(5, null, null)),
Tree(3,
Tree(6,
Tree(8, null, null),
Tree(9, null, null)),
null));

Put("preorder: ");
Preorder(N);
New_Line;
Put("inorder: ");
Inorder(N);
New_Line;
Put("postorder: ");
Postorder(N);
New_Line;
Put("level order: ");
Levelorder(N);
New_Line;
Destroy_Tree(N);
end Tree_traversal;

=== Parallel Solution ===
[[#References|[21]]]
In many ways, a tree is the perfect candidate for parallelism. In a tree, each
node/subtree is independent. As a result, we can split up a large tree into 2, 4, 8, or
more subtrees and hold subtree on each processor. Then, the only duplicated data
that must be kept on all processors is the tiny tip of the tree that is the parent of all
of the individual subtrees. Mathematically speaking, for a tree divided among n
processors (where n is a power of two), the processors only need to hold n – 1 nodes
in common – no matter how big the tree itself is. This is shown in the figure below. Since we are using 4 processors, we will only need 3 nodes in common. This is because one node is capable of having two branches. If the size of the tree was increased and the number of processors was also increased, the number of shared nodes would also increase to support the increased number of sub-trees.

The fact that trees are comprised of independent sub-trees makes parallelizing them
very easy. Properly done, the portion of these traversals that is parallelizable grows
at 2n for an n-generation tree, while the processors only need to synchronize once, at
the end, so parallelizable portion approaches 100% for large trees (but keep in mind [http://en.wikipedia.org/wiki/Amdahl's_law Amdahl’s Law],
footnote 1). The basic steps for parallelizing these traversals are as follows:

1. Perform the traversal on the parent part of the tree.
2. Whenever you get to a node that is only present on one processor, ask that processor to execute the appropriate C algorithm detailed above.
3. The processor will return its result that can be used exactly as if it was a serial processor.

[[File:parallel_tree.png]][[#References|[18]]]

A [http://www.cs.bu.edu/teaching/c/tree/breadth-first/ Breadth-First traversal] is somewhat more complicated to implement as a
parallel system because at each level, it must access nodes from all of the parallel
processors. Theoretically, a Breadth-First traversal can achieve the same 100%
code parallelization of Pre-, In-, and Post-Order traversals. However, the amount of processor to
processor data transmission adds in a greater potential for delays, thus slowing
down the algorithm. Nevertheless, as the size of the tree increases the size of the
generations grows at the rate of 2n while the number of synchronizations grows at a
rate of n for an n-generation tree, so the parallelizable portion of these traversals
also approaches 100%. The basic steps for parallelizing this traversal are as
follows:

1. Perform the traversal on the parent part of the tree.
2. Whenever you get to a node that is only present on one processor, ask that processor to execute the Breadth-First C algorithm detailed above,
but wait after it finishes one generation.
3. Combine all the one-generation results from the different processors in the correct order.
4. Allow each processor to execute the next generation of the Breadth-First C algorithm detailed above, and then wait again.
5. Repeat Steps 3 and 4 until there are no nodes remaining
[[#References|[18]]]

Here, since each processor is assigned an independent sub-tree, elaborate locks are not required.

Algorithm GEN-COMP-NEXT for Parallel Tree Traversal:
for all Pi, 1<=i<=n, do
parallel begin
Step 1: Processor Pi builds the jth field of i's parent node if i is the jth child of its parent.
The jth field (if it is not the last field) is stored in the ith index of array SUPERNODE.
Step 2: Processor Pi builds node i's last fiend whose array index is (n+1)
parallel end

To obtain the required tree-traversals, the following rules are operated on the linked list produced by algorithm GEN-COMP-NEXT:
pre-order traversal: select the first copy of each node;
post-order traversal: select the last copy of each node;
in-order traversal: delete the first copy of each node if it is not a leaf and delete the last copy of each node if it has more than one child.
This linked list can be locked while editing as per the LDS chapter in Solihin book. Either a Global lock approach, Fine Grained approach or [http://en.wikipedia.org/wiki/Readers%E2%80%93writer_lock Read-Write Locks] can be used.
In this fashion we have broken up the linked list of the tree into successive parts and imposed a divide-and-conquer technique to complete the traversal.

== Hash Tables ==
'''Hash Table Intro '''

Hash tables[[#References|[4]]] are very efficient data structures often used in searching algorithms for fast lookup operations. They are used extensively in data processing as in involves a vast amount of data through the hash table using as few indirection's in the storage structure as possible.

A single hash table level look can easily become a bottleneck, thus several method were developed to overcome this difficulty. Hash tables contain a series of "buckets" that function like indexes into an array, each of which can be accessed directly using their key value. The bucket for which a piece of data will be placed is determine by a special hashing function.

The major advantage of a hash table is that lookup times are essentially a constant value, much like an array with a known index. With a proper hashing function in place, it should be fairly rare that any 2 keys would generate the same value.

In the case that 2 keys do map to the same position, there is a conflict that must be dealt with in some fashion to obtain the correct value. One way that is relevant to linked list structures is to have a chained hash table in which a linked list is created with all values that have been placed in that particular bucket. The developer would have to not only take into account the proper bucket for the data being searched for, but also must considered the chained linked list. [[#References|[7]]]

There are several parallel implementations of hash tables available that use lock based synchronization. Larson et al. use two lock levels, there is one global table level lock, and there is one separate lightweight lock (a flag) for each bucket. The high level lock is just used for setting the bucket level flags and released right afterwards. This ensures a fine grained mutual exclusion (concurrent operations on bucket level), but needs only one real lock for the implementation.

A scalable hash table for shared memory multi-processor (SMP) supports very high rates of concurrent operations (e.g., insert, delete,
and lookup), while simultaneously reducing cache misses. The SMP system has a memory subsystem and a processor subsystem interconnected
via a bus structure.

The hash table is stored in the memory subsystem to facilitate access to data items. The hash table is segmented into multiple buckets,
with each bucket containing a reference to a linked list of bucket nodes that hold references to data items with keys that hash to a common value. Individual bucket nodes contain multiple signature-pointer pairs that reference corresponding data items.
Each signature-pointer pair has a hash signature computed from a key of the data item and a pointer to the data item. The first bucket
node in the linked list for each of the buckets is stored in the hash table.

To enable multithread access, while serializing operation of the table, the SMP system utilizes two levels of locks: a table lock and
multiple bucket locks. The table lock allows access by a single processing thread to the table while blocking access for other processing
threads. The table lock is held just long enough for the thread to acquire the bucket lock of a particular bucket node. Once the table lock
is released, another thread can access the hash table and any one of the other buckets.

[[File:315px-Hash table 3 1 1 0 1 0 0 SP.svg.png]]

=== Opportunities for Parallelization ===

Hash tables can be very well suited to parallel applications. For example, system code responsible for caching between multiple processors could itself be an ideal opportunity for a shared hashmap. Each processor sharing one common cache would be able to access the relevant information all in one location.

This would, however, involve a good bit of synchronization, as each processor would need to wait in case a lock was being placed on a specific bucket in the cache hashmap. Unfortunately, traditional locking would be a bad solution to this problem as processors need to run very quickly. Having to wait for locks would destroy the application processing time. The need for a non-locking solution is critical to performance.

In Java, the standard class utilized for hashing is the HashMap[[#References|[17]]] class. This class has a fundamental weakness though in that the entire map requires synchronization prior to each access. This causes a lot of contention and many bottlenecks on a parallel machine.

Below, I will present a Java-based solution to this problem by using a ConcurrentHashMap class. This class only requires a portion of the map to be locked and reads can generally occur with no locking whatsoever.

=== HashMap Code with Locking ===

''' Simple synchronized example to increment a counter.'''[[#References|[9]]]
private Map<String,Integer> queryCounts = new HashMap<String,Integer>(1000);
private '''synchronized''' void incrementCount(String q) {
Integer cnt = queryCounts.get(q);
if (cnt == null) {
queryCounts.put(q, 1);
} else {
queryCounts.put(q, cnt + 1);
}
}

The above code was written using an ordinary HashMap data structure. Notice that we use the synchronized keyword here to signify that only one thread can enter this function at any one point in time. With a really large number of threads, however, waiting to enter the synchronized operation could be a major bottleneck.

''' Iterator example for synchronized HashMap.'''

Map m = Collections.synchronizedMap(new HashMap());
Set s = m.keySet(); // set of keys in hashmap
synchronized(m) { // synchronizing on map
Iterator i = s.iterator(); // Must be in synchronized block
while (i.hasNext())
foo(i.next());
}

In the above example, we show how an iterator could be used to traverse over a map. In this case, we would need to utilize the synchronizedMap function available in the Collections interface. Also, as you may notice, once the iterator code begins we must actually synchronize on the entire map in order to iterate through the results. But what if several processors wish to iterate through at the same time?

=== Parallel Code Solution ===

The key issue in a hash table in a parallel environment is to make sure any update/insert/delete sequences have been completed properly prior to attempting subsequent operations to make sure the data has been synched appropriately. However, since access speed is such a critical component of the design of a hash table, it is essential to try and avoid using too many locks for performing synchronization. Fortunately, a number of lock-free hash designs have been implemented to avoid this bottleneck.

One such example in Java is the ConcurrentHashMap[[#References|[9]]], which acts as a synchronized version of the [http://docs.oracle.com/javase/6/docs/api/java/util/HashMap.html HashMap]. With this structure, there is full concurrency of retrievals and adjustable expected concurrency for updates. There is, however, no locking in this data structure and retrievals will typically run in parallel along with updates/deletes. Retrievals, however, will receive all most recently completed transactions even if it cannot get the values that haven't finished being updated. This both allows for efficiency and greater concurrency.

'''Parallel Counter Increment Alternative:'''

private ConcurrentMap<String,Integer> queryCounts =
new ConcurrentHashMap<String,Integer>(1000);
private void incrementCount(String q) {
Integer oldVal, newVal;
do {
oldVal = queryCounts.get(q);
newVal = (oldVal == null) ? 1 : (oldVal + 1);
} while (!queryCounts.replace(q, oldVal, newVal));
}

The above code snippet represents an alternative to the serial option presented in the previous section, while also avoiding much of the locking that takes place using the synchronized functions or synchronized blocks. With ConcurrentHashMap, however, notice that we must implement some new code in order to handle the fact that a variety of inserts/updates could be running at the same time. The replace() function here acts much like a compare-and-set operation typically used with concurrent code. Basically, the value would be changed only if not equal to the previously mapped value. This is much more efficient that locking the entire function as we often do not expect unequal values.

'''Parallel Traversal Alternative:'''

Map m = new ConcurrentHashMap();
Set s = m.keySet(); // set of keys in hashmap
Iterator i = s.iterator(); // Must be in synchronized block
while (i.hasNext())
foo(i.next());

In the case of a traversal, recall that ConcurrentHashMaps require to locking on read operations. Thus we can actually remove the synchronized condition here and iterate in a normal fashion.

== Graphs ==
=== Graph Intro ===

A graph data structure[[#References|[10]]] is another type of linked-list structure that focuses on data relationships and the most efficient ways to traverse from one node to another. For example, in a networking application, one network node may have connections to a variety of other network nodes. These nodes then also link to a variety of other nodes in the network. Using this connection of nodes, it would be possible to then find a path from one specific node to another in the chain. This could be accomplished by having each node contain a linked list of pointers to all other reachable nodes.

[[File:250px-6n-graf.svg.png]]

=== Opportunities for Parallelization ===

Graphs[[#References|[10]]] consist of a finite set of ordered pairs called edges or arcs, of certain entities called nodes or vertices. From one given vertex, one would typically want to order the different paths from one vertex to another using its list of edges or, more than likely, would be interested in the fastest means of getting from one of these vertexes to some sort of destination vertex.

Graph nodes typically will keep their list of edges in a linked list. Also, when attempting to create a shortest path algorithm on the fly, the graph will typically use a combination of a linked list to represent the path as it's being built, along with a queue that is used for each step of that process. Synchronizing all of these can be a major challenge.

Much like the hash table, graphs cannot afford to be slow and must often generate results in a very efficient manner. Having to lock on each list of edges or locking on a shortest path list would really be a major obstacle.

Certainly though, the need for parallel processing becomes critical when you consider, for example, that social networking has become such a major proponent of graph algorithms. Facebook now has roughly a billion users[[#References|[15]]] and each user has series of friend links that must be analyzed and examined. This list just keeps growing and growing.

One of the most significant opportunities for a parallel algorithm with a graph data structure is with the traversal algorithms. We can use Breadth-First search[[#References|[16]]] as an example of this, starting from an initial node and expanding outwards until reaching the destination node.

=== Breadth First Search - Serial Version ===

The following shows a sample of a bread first algorithm which traverses from the city of Frankfurt to Augsburg and Stuttgart Germany. In does so, the graph begins at a root node (Frankfurt) and expands outwardly to all connected nodes on each step. From there, each of those nodes proceeds to expand the search outwards until all nodes have been covered.

[[File:GermanyBFS.png]][[#References|[13]]]

The following code snippet implements a BFS search function. This function utilized coloring schemes and marks to denote that a node has been visited. It begins with an initial vertex in a queue and expands outward to all its successors until no further elements remain unmarked.[[#References|[12]]]

public void search(Graph g)
{
g.paint(Color.white); // paint all the graph vertices with white
g.mark(false); // unmark the whole graph
refresh(null); // and redraw it
Vertex r = g.root(); // the root is painted grey
g.paint(r, Color.gray); refresh(g.box(r));
java.util.Vector queue = new java.util.Vector();
queue.addElement(r); // and put in a queue
while(!queue.isEmpty())
{
Vertex u = (Vertex) queue.firstElement();
queue.removeElement(u); // extract a vertex from the queue
g.mark(u, true); refresh(g.box(u));
int dp = g.degreePlus(u);
for(int i = 0; i < dp; i++) // look at its successors
{
Vertex v = g.ithSucc(i, u);
if(Color.white == g.color(v))
{
queue.addElement(v);
g.paint(v, Color.gray); refresh(g.box(v));
}
}
g.paint(u, Color.black); refresh(g.box(u));
g.mark(u, false); refresh(g.box(u));
}
}

=== Parallel Solution ===

But could we introduce parallel mechanisms into this Breadth First search? The most logical and effective way, instead of utilizing locks and synchronized regions, is to use data parallel techniques during the traversal. This can be accomplished by having each node of a given breadth search step be sent to a separate processor. So, using the above example, instead of having Frankfurt->Mannheim followed by Frankfurt->Wurzburg followed by Frankfurt->Bassel on the same processor, Frankfurt could split out all 3 searches in a parallel fashion onto 3 different processors. Then, possible some cleanup code would be left at the end to visit any remaining untouched nodes. In a network routing applications, being able to split up the search for each IP address code would make searched significantly faster that allowing one processor to be a bottleneck.

Using locking pseudocode, you might have an algorithm similar to this:

for all vertices u at level d in parallel do
for all adjacencies v of u in parallel do
dv = D[v];
if(dv < 0) // v is visited for the first time
vis = fetch_and_add(&Visited[v], 1); '''LOCK'''
if(vis == 0) // v is added to a stack only once
D[v] = d+1;
pS[count++] = v; // Add v to local thread stack
fetch_and_add(&sigma[v], sigma[u]); '''LOCK'''
fetch_and_add(&Pcount[v], 1); // Add u to predecessor list of v '''LOCK'''
if(dv == d + 1)
fetch_and_add(&sigma[v], sigma[u]); '''LOCK'''
fetch_and_add(&Pcount[v], 1); // Add u to predecessor list of v '''LOCK'''

A much better parallel algorithm is represented in the following pseudocode. Notice that each of the vertices is sent to a separate processor and send/receive operations will eventually sync up the path information.

[[File:Parallel-code.PNG]][[#References|[14]]]

The following graph also shows how now each of the regional sets of vertices being search can be added to the path in a parallel fashion.

[[File:Parallel-graph.PNG]][[#References|[11]]]

Every set of vertices in the same distance from the source is assigned to a processor. This set of vertices is called a regional set of vertices. The goal is to find the shortest path connecting each region.

= Quiz =

1. Describe the copy-scan technique.

2. Describe the pointer doubling technique.

3. Which concurrency issues are of the most concern in a tree data structure?

4. What is the alternative to using a copy-scan technique in pointer-based programming?

5. Which concurrency issues are of the most concern with hash table data structures?

6. Which concurrency issues are of the most concern with graph data structures?

7. Why would you not want locking mechanisms in hash tables?

8. What is the nature of the linked list in a tree structure?

9. Describe a parallel alternative in the tree data structure.

10. Describe a parallel alternative in a graph data structure.

= References =

#http://people.engr.ncsu.edu/efg/506/s01/lectures/notes/lec8.html
#http://en.wikipedia.org/wiki/Tree_%28data_structure%29
#http://oreilly.com/catalog/masteralgoc/chapter/ch08.pdf
#http://www.devjavasoft.org/code/classhashtable.html
#http://osr600doc.sco.com/en/SDK_c++/_Intro_graph.html
#http://web.eecs.utk.edu/~berry/cs302s02/src/code/Chap14/Graph.java
#http://en.wikipedia.org/wiki/File:Hash_table_3_1_1_0_1_0_0_SP.svg
#http://rosettacode.org/wiki/Talk:Tree_traversal
#http://www.javamex.com/tutorials/synchronization_concurrency_8_hashmap.shtml
#http://en.wikipedia.org/wiki/Graph_%28abstract_data_type%29
#http://www.cc.gatech.edu/~bader/papers/PPoPP12/PPoPP-2012-part2.pdf
#http://renaud.waldura.com/portfolio/graph-algorithms/classes/graph/BFSearch.java
#http://en.wikipedia.org/w/index.php?title=File%3AGermanyBFS.svg
#http://sc05.supercomputing.org/schedule/pdf/pap346.pdf
#http://www.facebook.com/press/info.php?statistics
#http://en.wikipedia.org/wiki/Breadth-first_search
#http://code.wikia.com/wiki/Hashmap
#http://www.shodor.org/petascale/materials/UPModules/Binary_Tree_Traversal
#http://en.wikipedia.org/wiki/Readers%E2%80%93writer_lock
#http://dl.acm.org/citation.cfm?id=320078
#http://en.wikipedia.org/wiki/Tree_traversal
P.-A. Larson, M. R. Krishnan,and G. V. Reilly, “Scaleable hash table for
shared-memory multiprocessor system,” US Patent number: 6578131,
2003
http://ww2.cs.mu.oz.au/~pjs/papers/paralleldp.pdf

CSC/ECE 506 Spring 2014/5a rm

2014-02-26T05:13:23Z

Remcelfr:

= Chapter 5a CSC/ECE 506 Spring 2014 / Other linked data structures =

Original wiki : http://wiki.expertiza.ncsu.edu/index.php/CSC/ECE_506_Spring_2013/5a_ks

= Overview =

Linked Data Structures (LDS) consists of different types of data structures such as [http://en.wikipedia.org/wiki/Linked_list linked lists], [http://en.wikibooks.org/wiki/Data_Structures/Trees trees], [http://en.wikipedia.org/wiki/Hash_table hash tables] and [http://en.wikibooks.org/wiki/Data_Structures/Graphs graphs]. Although each structure is diversed, LDS traversal shares a common characteristic in reading a node and discovering the other nodes it points to. Hence, this often introduces loop carried dependence. Chapter 5 of Solihin, discusses various algorithms on parallelizing LDS using a simple linked list. In this wiki, we attempt to cover other LDS such as trees, hashes and graphs, and how the parallelization algorithms discussed can be applied to these structures. This wiki explores concurrency problems related to each type and possible solutions for parallelizing them.

= Introduction to Linked-List Parallel Programming =

One component that tends to link together various data structures is their reliance at some level on an internal pointer-based linked list. For example, hash tables have linked lists to support chained links to a given bucket in order to resolve collisions, trees have linked lists with left and right tree node paths, and graphs have linked lists to determine shortest path algorithms.

But what mechanism allows us to generate parallel algorithms for these structures?

For an array processing algorithm, a common technique used at the processor level is the copy-scan technique. This technique involves copying rows of data from one processor to another in a log(n) fashion until all processors have their own copy of that row. From there, you could perform a reduction technique to generate a sum of all the data, all while working in a parallel fashion. Take the following grid:[[#References|[1]]]

The basic process for copy-scan would be to:
Step 1) Copy the row 1 array to row 2.
Step 2) Copy the row 1 array to row 3, row 2 to row 4, etc on the next run.
Step 3) Continue in this manner until all rows have been copied in a log(n) fashion.
Step 4) Perform the parallel operations to generate the desired result (reduction for sum, etc.).

[[File:CopyScan.gif]]

But how does this same process work in the linked list world?

With linked lists, there is a concept called pointer doubling, which works in a very similar manner to copy-scan.[[#References|[1]]]

Step 1) Each processor will make a copy of the pointer it holds to its neighbor.
Step 2) Next, each processor will make a pointer to the processor 2 steps away.
Step 3) This continues in logarithmic fashion until each processor has a pointer to the end of the chain.
Step 4) Perform the parallel operations to generate the desired result.

One of the uses for pointer doubling is to perform partial sums of a linked list. The way that this is accomplished is by adding the value held by the node with the value stored in the node it is pointing to. This is repeated until all pointers have reached the end of the list. The result is a linked list which contains the sum of the node and all preceding nodes. Below shows and example of this operation in action.

[[File:PartialSums1.png]]

[[File:PartialSums2.png]]

[[File:PartialSums3.png]]

[[File:PartialSums4.png]]

However, with linked list programming, similar to array-based programming, it becomes imperative to have some sort of locking mechanism or other parallel technique for [http://en.wikipedia.org/wiki/Critical_section critical sections] in order to avoid [http://en.wikipedia.org/wiki/Race_condition race conditions]. To make sure the results are correct, it is important that operations can be serialized appropriately and that data remains current and synchronized.

In this chapter, we will explore 3 linked-list based data structures and the parallelization opportunities as well as the concurrency issues they present: hash tables, trees, and graphs.

== Trees ==

=== Tree Intro ===

A tree data structure [[#References|[2]]] contains a set of ordered nodes with one parent node followed by zero or more child nodes. Typically this tree structure is used with searching or sorting algorithms to achieve log(n) efficiencies. Assuming you have a balanced tree, or a relatively equal set of nodes under each branching structure of the tree, and assuming a proper ordering structure, searches/inserts/deletes should occur far more quickly than having to traverse an entire list.

=== Opportunities for Parallelization ===

One potential slowdown in a tree data structure could occur during the traversal process. Even though search/update/insert can occur in a logarithmic fashion, traversal operations such as in-order, pre-order, post-order traversals can still require a full sequence of the list to generate all output. This gives an opportunity to generate parallel code by having various portions of the traversal occur on different processors.

=== Serial Code Example ===

Below is a code[[#References|[8]]] for serial tree traversal algorithms
with behavior as the figure below shows:

[[File: tree.PNG]]

procedure Tree_Traversal is
type Node;
type Node_Access is access Node;
type Node is record
Left : Node_Access := null;
Right : Node_Access := null;
Data : Integer;
end record;

procedure Destroy_Tree(N : in out Node_Access) is
procedure free is new Ada.Unchecked_Deallocation(Node, Node_Access);
begin
if N.Left /= null then
Destroy_Tree(N.Left);
end if;
if N.Right /= null then
Destroy_Tree(N.Right);
end if;
Free(N);
end Destroy_Tree;

function Tree(Value : Integer; Left : Node_Access; Right : Node_Access) return Node_Access is
Temp : Node_Access := new Node;
begin
Temp.Data := Value;
Temp.Left := Left;
Temp.Right := Right;
return Temp;
end Tree;

procedure Preorder(N : Node_Access) is
begin
Put(Integer'Image(N.Data));
if N.Left /= null then
Preorder(N.Left);
end if;
if N.Right /= null then
Preorder(N.Right);
end if;
end Preorder;

procedure Inorder(N : Node_Access) is
begin
if N.Left /= null then
Inorder(N.Left);
end if;
Put(Integer'Image(N.Data));
if N.Right /= null then
Inorder(N.Right);
end if;
end Inorder;

procedure Postorder(N : Node_Access) is
begin
if N.Left /= null then
Postorder(N.Left);
end if;
if N.Right /= null then
Postorder(N.Right);
end if;
Put(Integer'Image(N.Data));
end Postorder;

procedure Levelorder(N : Node_Access) is
package Queues is new Ada.Containers.Doubly_Linked_Lists(Node_Access);
use Queues;
Node_Queue : List;
Next : Node_Access;
begin
Node_Queue.Append(N);
while not Is_Empty(Node_Queue) loop
Next := First_Element(Node_Queue);
Delete_First(Node_Queue);
Put(Integer'Image(Next.Data));
if Next.Left /= null then
Node_Queue.Append(Next.Left);
end if;
if Next.Right /= null then
Node_Queue.Append(Next.Right);
end if;
end loop;
end Levelorder;

N : Node_Access;
begin
N := Tree(1,
Tree(2,
Tree(4,
Tree(7, null, null),
null),
Tree(5, null, null)),
Tree(3,
Tree(6,
Tree(8, null, null),
Tree(9, null, null)),
null));

Put("preorder: ");
Preorder(N);
New_Line;
Put("inorder: ");
Inorder(N);
New_Line;
Put("postorder: ");
Postorder(N);
New_Line;
Put("level order: ");
Levelorder(N);
New_Line;
Destroy_Tree(N);
end Tree_traversal;

=== Parallel Solution ===
[[#References|[21]]]
In many ways, a tree is the perfect candidate for parallelism. In a tree, each
node/subtree is independent. As a result, we can split up a large tree into 2, 4, 8, or
more subtrees and hold subtree on each processor. Then, the only duplicated data
that must be kept on all processors is the tiny tip of the tree that is the parent of all
of the individual subtrees. Mathematically speaking, for a tree divided among n
processors (where n is a power of two), the processors only need to hold n – 1 nodes
in common – no matter how big the tree itself is.
The fact that trees are comprised of independent sub-trees makes parallelizing them
very easy. Properly done, the portion of these traversals that is parallelizable grows
at 2n for an n-generation tree, while the processors only need to synchronize once, at
the end, so parallelizable portion approaches 100% for large trees (but keep in mind [http://en.wikipedia.org/wiki/Amdahl's_law Amdahl’s Law],
footnote 1). The basic steps for parallelizing these traversals are as follows:

1. Perform the traversal on the parent part of the tree.
2. Whenever you get to a node that is only present on one processor, ask that processor to execute the appropriate C algorithm detailed above.
3. The processor will return its result that can be used exactly as if it was a serial processor.

[[File:parallel_tree.png]][[#References|[18]]]

A [http://www.cs.bu.edu/teaching/c/tree/breadth-first/ Breadth-First traversal] is somewhat more complicated to implement as a
parallel system because at each level, it must access nodes from all of the parallel
processors. Theoretically, a Breadth-First traversal can achieve the same 100%
code parallelization of Pre-, In-, and Post-Order traversals. However, the amount of processor to
processor data transmission adds in a greater potential for delays, thus slowing
down the algorithm. Nevertheless, as the size of the tree increases the size of the
generations grows at the rate of 2n while the number of synchronizations grows at a
rate of n for an n-generation tree, so the parallelizable portion of these traversals
also approaches 100%. The basic steps for parallelizing this traversal are as
follows:

1. Perform the traversal on the parent part of the tree.
2. Whenever you get to a node that is only present on one processor, ask that processor to execute the Breadth-First C algorithm detailed above,
but wait after it finishes one generation.
3. Combine all the one-generation results from the different processors in the correct order.
4. Allow each processor to execute the next generation of the Breadth-First C algorithm detailed above, and then wait again.
5. Repeat Steps 3 and 4 until there are no nodes remaining
[[#References|[18]]]

Here, since each processor is assigned an independent sub-tree, elaborate locks are not required.

Algorithm GEN-COMP-NEXT for Parallel Tree Traversal:
for all Pi, 1<=i<=n, do
parallel begin
Step 1: Processor Pi builds the jth field of i's parent node if i is the jth child of its parent.
The jth field (if it is not the last field) is stored in the ith index of array SUPERNODE.
Step 2: Processor Pi builds node i's last fiend whose array index is (n+1)
parallel end

To obtain the required tree-traversals, the following rules are operated on the linked list produced by algorithm GEN-COMP-NEXT:
pre-order traversal: select the first copy of each node;
post-order traversal: select the last copy of each node;
in-order traversal: delete the first copy of each node if it is not a leaf and delete the last copy of each node if it has more than one child.
This linked list can be locked while editing as per the LDS chapter in Solihin book. Either a Global lock approach, Fine Grained approach or [http://en.wikipedia.org/wiki/Readers%E2%80%93writer_lock Read-Write Locks] can be used.
In this fashion we have broken up the linked list of the tree into successive parts and imposed a divide-and-conquer technique to complete the traversal.

== Hash Tables ==
'''Hash Table Intro '''

Hash tables[[#References|[4]]] are very efficient data structures often used in searching algorithms for fast lookup operations. They are used extensively in data processing as in involves a vast amount of data through the hash table using as few indirection's in the storage structure as possible.

A single hash table level look can easily become a bottleneck, thus several method were developed to overcome this difficulty. Hash tables contain a series of "buckets" that function like indexes into an array, each of which can be accessed directly using their key value. The bucket for which a piece of data will be placed is determine by a special hashing function.

The major advantage of a hash table is that lookup times are essentially a constant value, much like an array with a known index. With a proper hashing function in place, it should be fairly rare that any 2 keys would generate the same value.

In the case that 2 keys do map to the same position, there is a conflict that must be dealt with in some fashion to obtain the correct value. One way that is relevant to linked list structures is to have a chained hash table in which a linked list is created with all values that have been placed in that particular bucket. The developer would have to not only take into account the proper bucket for the data being searched for, but also must considered the chained linked list. [[#References|[7]]]

There are several parallel implementations of hash tables available that use lock based synchronization. Larson et al. use two lock levels, there is one global table level lock, and there is one separate lightweight lock (a flag) for each bucket. The high level lock is just used for setting the bucket level flags and released right afterwards. This ensures a fine grained mutual exclusion (concurrent operations on bucket level), but needs only one real lock for the implementation.

A scalable hash table for shared memory multi-processor (SMP) supports very high rates of concurrent operations (e.g., insert, delete,
and lookup), while simultaneously reducing cache misses. The SMP system has a memory subsystem and a processor subsystem interconnected
via a bus structure.

The hash table is stored in the memory subsystem to facilitate access to data items. The hash table is segmented into multiple buckets,
with each bucket containing a reference to a linked list of bucket nodes that hold references to data items with keys that hash to a common value. Individual bucket nodes contain multiple signature-pointer pairs that reference corresponding data items.
Each signature-pointer pair has a hash signature computed from a key of the data item and a pointer to the data item. The first bucket
node in the linked list for each of the buckets is stored in the hash table.

To enable multithread access, while serializing operation of the table, the SMP system utilizes two levels of locks: a table lock and
multiple bucket locks. The table lock allows access by a single processing thread to the table while blocking access for other processing
threads. The table lock is held just long enough for the thread to acquire the bucket lock of a particular bucket node. Once the table lock
is released, another thread can access the hash table and any one of the other buckets.

[[File:315px-Hash table 3 1 1 0 1 0 0 SP.svg.png]]

=== Opportunities for Parallelization ===

Hash tables can be very well suited to parallel applications. For example, system code responsible for caching between multiple processors could itself be an ideal opportunity for a shared hashmap. Each processor sharing one common cache would be able to access the relevant information all in one location.

This would, however, involve a good bit of synchronization, as each processor would need to wait in case a lock was being placed on a specific bucket in the cache hashmap. Unfortunately, traditional locking would be a bad solution to this problem as processors need to run very quickly. Having to wait for locks would destroy the application processing time. The need for a non-locking solution is critical to performance.

In Java, the standard class utilized for hashing is the HashMap[[#References|[17]]] class. This class has a fundamental weakness though in that the entire map requires synchronization prior to each access. This causes a lot of contention and many bottlenecks on a parallel machine.

Below, I will present a Java-based solution to this problem by using a ConcurrentHashMap class. This class only requires a portion of the map to be locked and reads can generally occur with no locking whatsoever.

=== HashMap Code with Locking ===

''' Simple synchronized example to increment a counter.'''[[#References|[9]]]
private Map<String,Integer> queryCounts = new HashMap<String,Integer>(1000);
private '''synchronized''' void incrementCount(String q) {
Integer cnt = queryCounts.get(q);
if (cnt == null) {
queryCounts.put(q, 1);
} else {
queryCounts.put(q, cnt + 1);
}
}

The above code was written using an ordinary HashMap data structure. Notice that we use the synchronized keyword here to signify that only one thread can enter this function at any one point in time. With a really large number of threads, however, waiting to enter the synchronized operation could be a major bottleneck.

''' Iterator example for synchronized HashMap.'''

Map m = Collections.synchronizedMap(new HashMap());
Set s = m.keySet(); // set of keys in hashmap
synchronized(m) { // synchronizing on map
Iterator i = s.iterator(); // Must be in synchronized block
while (i.hasNext())
foo(i.next());
}

In the above example, we show how an iterator could be used to traverse over a map. In this case, we would need to utilize the synchronizedMap function available in the Collections interface. Also, as you may notice, once the iterator code begins we must actually synchronize on the entire map in order to iterate through the results. But what if several processors wish to iterate through at the same time?

=== Parallel Code Solution ===

The key issue in a hash table in a parallel environment is to make sure any update/insert/delete sequences have been completed properly prior to attempting subsequent operations to make sure the data has been synched appropriately. However, since access speed is such a critical component of the design of a hash table, it is essential to try and avoid using too many locks for performing synchronization. Fortunately, a number of lock-free hash designs have been implemented to avoid this bottleneck.

One such example in Java is the ConcurrentHashMap[[#References|[9]]], which acts as a synchronized version of the [http://docs.oracle.com/javase/6/docs/api/java/util/HashMap.html HashMap]. With this structure, there is full concurrency of retrievals and adjustable expected concurrency for updates. There is, however, no locking in this data structure and retrievals will typically run in parallel along with updates/deletes. Retrievals, however, will receive all most recently completed transactions even if it cannot get the values that haven't finished being updated. This both allows for efficiency and greater concurrency.

'''Parallel Counter Increment Alternative:'''

private ConcurrentMap<String,Integer> queryCounts =
new ConcurrentHashMap<String,Integer>(1000);
private void incrementCount(String q) {
Integer oldVal, newVal;
do {
oldVal = queryCounts.get(q);
newVal = (oldVal == null) ? 1 : (oldVal + 1);
} while (!queryCounts.replace(q, oldVal, newVal));
}

The above code snippet represents an alternative to the serial option presented in the previous section, while also avoiding much of the locking that takes place using the synchronized functions or synchronized blocks. With ConcurrentHashMap, however, notice that we must implement some new code in order to handle the fact that a variety of inserts/updates could be running at the same time. The replace() function here acts much like a compare-and-set operation typically used with concurrent code. Basically, the value would be changed only if not equal to the previously mapped value. This is much more efficient that locking the entire function as we often do not expect unequal values.

'''Parallel Traversal Alternative:'''

Map m = new ConcurrentHashMap();
Set s = m.keySet(); // set of keys in hashmap
Iterator i = s.iterator(); // Must be in synchronized block
while (i.hasNext())
foo(i.next());

In the case of a traversal, recall that ConcurrentHashMaps require to locking on read operations. Thus we can actually remove the synchronized condition here and iterate in a normal fashion.

== Graphs ==
=== Graph Intro ===

A graph data structure[[#References|[10]]] is another type of linked-list structure that focuses on data relationships and the most efficient ways to traverse from one node to another. For example, in a networking application, one network node may have connections to a variety of other network nodes. These nodes then also link to a variety of other nodes in the network. Using this connection of nodes, it would be possible to then find a path from one specific node to another in the chain. This could be accomplished by having each node contain a linked list of pointers to all other reachable nodes.

[[File:250px-6n-graf.svg.png]]

=== Opportunities for Parallelization ===

Graphs[[#References|[10]]] consist of a finite set of ordered pairs called edges or arcs, of certain entities called nodes or vertices. From one given vertex, one would typically want to order the different paths from one vertex to another using its list of edges or, more than likely, would be interested in the fastest means of getting from one of these vertexes to some sort of destination vertex.

Graph nodes typically will keep their list of edges in a linked list. Also, when attempting to create a shortest path algorithm on the fly, the graph will typically use a combination of a linked list to represent the path as it's being built, along with a queue that is used for each step of that process. Synchronizing all of these can be a major challenge.

Much like the hash table, graphs cannot afford to be slow and must often generate results in a very efficient manner. Having to lock on each list of edges or locking on a shortest path list would really be a major obstacle.

Certainly though, the need for parallel processing becomes critical when you consider, for example, that social networking has become such a major proponent of graph algorithms. Facebook now has roughly a billion users[[#References|[15]]] and each user has series of friend links that must be analyzed and examined. This list just keeps growing and growing.

One of the most significant opportunities for a parallel algorithm with a graph data structure is with the traversal algorithms. We can use Breadth-First search[[#References|[16]]] as an example of this, starting from an initial node and expanding outwards until reaching the destination node.

=== Breadth First Search - Serial Version ===

The following shows a sample of a bread first algorithm which traverses from the city of Frankfurt to Augsburg and Stuttgart Germany. In does so, the graph begins at a root node (Frankfurt) and expands outwardly to all connected nodes on each step. From there, each of those nodes proceeds to expand the search outwards until all nodes have been covered.

[[File:GermanyBFS.png]][[#References|[13]]]

The following code snippet implements a BFS search function. This function utilized coloring schemes and marks to denote that a node has been visited. It begins with an initial vertex in a queue and expands outward to all its successors until no further elements remain unmarked.[[#References|[12]]]

public void search(Graph g)
{
g.paint(Color.white); // paint all the graph vertices with white
g.mark(false); // unmark the whole graph
refresh(null); // and redraw it
Vertex r = g.root(); // the root is painted grey
g.paint(r, Color.gray); refresh(g.box(r));
java.util.Vector queue = new java.util.Vector();
queue.addElement(r); // and put in a queue
while(!queue.isEmpty())
{
Vertex u = (Vertex) queue.firstElement();
queue.removeElement(u); // extract a vertex from the queue
g.mark(u, true); refresh(g.box(u));
int dp = g.degreePlus(u);
for(int i = 0; i < dp; i++) // look at its successors
{
Vertex v = g.ithSucc(i, u);
if(Color.white == g.color(v))
{
queue.addElement(v);
g.paint(v, Color.gray); refresh(g.box(v));
}
}
g.paint(u, Color.black); refresh(g.box(u));
g.mark(u, false); refresh(g.box(u));
}
}

=== Parallel Solution ===

But could we introduce parallel mechanisms into this Breadth First search? The most logical and effective way, instead of utilizing locks and synchronized regions, is to use data parallel techniques during the traversal. This can be accomplished by having each node of a given breadth search step be sent to a separate processor. So, using the above example, instead of having Frankfurt->Mannheim followed by Frankfurt->Wurzburg followed by Frankfurt->Bassel on the same processor, Frankfurt could split out all 3 searches in a parallel fashion onto 3 different processors. Then, possible some cleanup code would be left at the end to visit any remaining untouched nodes. In a network routing applications, being able to split up the search for each IP address code would make searched significantly faster that allowing one processor to be a bottleneck.

Using locking pseudocode, you might have an algorithm similar to this:

for all vertices u at level d in parallel do
for all adjacencies v of u in parallel do
dv = D[v];
if(dv < 0) // v is visited for the first time
vis = fetch_and_add(&Visited[v], 1); '''LOCK'''
if(vis == 0) // v is added to a stack only once
D[v] = d+1;
pS[count++] = v; // Add v to local thread stack
fetch_and_add(&sigma[v], sigma[u]); '''LOCK'''
fetch_and_add(&Pcount[v], 1); // Add u to predecessor list of v '''LOCK'''
if(dv == d + 1)
fetch_and_add(&sigma[v], sigma[u]); '''LOCK'''
fetch_and_add(&Pcount[v], 1); // Add u to predecessor list of v '''LOCK'''

A much better parallel algorithm is represented in the following pseudocode. Notice that each of the vertices is sent to a separate processor and send/receive operations will eventually sync up the path information.

[[File:Parallel-code.PNG]][[#References|[14]]]

The following graph also shows how now each of the regional sets of vertices being search can be added to the path in a parallel fashion.

[[File:Parallel-graph.PNG]][[#References|[11]]]

Every set of vertices in the same distance from the source is assigned to a processor. This set of vertices is called a regional set of vertices. The goal is to find the shortest path connecting each region.

= Quiz =

1. Describe the copy-scan technique.

2. Describe the pointer doubling technique.

3. Which concurrency issues are of the most concern in a tree data structure?

4. What is the alternative to using a copy-scan technique in pointer-based programming?

5. Which concurrency issues are of the most concern with hash table data structures?

6. Which concurrency issues are of the most concern with graph data structures?

7. Why would you not want locking mechanisms in hash tables?

8. What is the nature of the linked list in a tree structure?

9. Describe a parallel alternative in the tree data structure.

10. Describe a parallel alternative in a graph data structure.

= References =

#http://people.engr.ncsu.edu/efg/506/s01/lectures/notes/lec8.html
#http://en.wikipedia.org/wiki/Tree_%28data_structure%29
#http://oreilly.com/catalog/masteralgoc/chapter/ch08.pdf
#http://www.devjavasoft.org/code/classhashtable.html
#http://osr600doc.sco.com/en/SDK_c++/_Intro_graph.html
#http://web.eecs.utk.edu/~berry/cs302s02/src/code/Chap14/Graph.java
#http://en.wikipedia.org/wiki/File:Hash_table_3_1_1_0_1_0_0_SP.svg
#http://rosettacode.org/wiki/Talk:Tree_traversal
#http://www.javamex.com/tutorials/synchronization_concurrency_8_hashmap.shtml
#http://en.wikipedia.org/wiki/Graph_%28abstract_data_type%29
#http://www.cc.gatech.edu/~bader/papers/PPoPP12/PPoPP-2012-part2.pdf
#http://renaud.waldura.com/portfolio/graph-algorithms/classes/graph/BFSearch.java
#http://en.wikipedia.org/w/index.php?title=File%3AGermanyBFS.svg
#http://sc05.supercomputing.org/schedule/pdf/pap346.pdf
#http://www.facebook.com/press/info.php?statistics
#http://en.wikipedia.org/wiki/Breadth-first_search
#http://code.wikia.com/wiki/Hashmap
#http://www.shodor.org/petascale/materials/UPModules/Binary_Tree_Traversal
#http://en.wikipedia.org/wiki/Readers%E2%80%93writer_lock
#http://dl.acm.org/citation.cfm?id=320078
#http://en.wikipedia.org/wiki/Tree_traversal
P.-A. Larson, M. R. Krishnan,and G. V. Reilly, “Scaleable hash table for
shared-memory multiprocessor system,” US Patent number: 6578131,
2003
http://ww2.cs.mu.oz.au/~pjs/papers/paralleldp.pdf

CSC/ECE 506 Spring 2014/5a rm

2014-02-26T03:26:35Z

Remcelfr:

= Chapter 5a CSC/ECE 506 Spring 2014 / Other linked data structures =

Original wiki : http://wiki.expertiza.ncsu.edu/index.php/CSC/ECE_506_Spring_2013/5a_ks

= Overview =

Linked Data Structures (LDS) consists of different types of data structures such as [http://en.wikipedia.org/wiki/Linked_list linked lists], [http://en.wikibooks.org/wiki/Data_Structures/Trees trees], [http://en.wikipedia.org/wiki/Hash_table hash tables] and [http://en.wikibooks.org/wiki/Data_Structures/Graphs graphs]. Although each structure is diversed, LDS traversal shares a common characteristic in reading a node and discovering the other nodes it points to. Hence, this often introduces loop carried dependence. Chapter 5 of Solihin, discusses various algorithms on parallelizing LDS using a simple linked list. In this wiki, we attempt to cover other LDS such as trees, hashes and graphs, and how the parallelization algorithms discussed can be applied to these structures. This wiki explores concurrency problems related to each type and possible solutions for parallelizing them.

= Introduction to Linked-List Parallel Programming =

One component that tends to link together various data structures is their reliance at some level on an internal pointer-based linked list. For example, hash tables have linked lists to support chained links to a given bucket in order to resolve collisions, trees have linked lists with left and right tree node paths, and graphs have linked lists to determine shortest path algorithms.

But what mechanism allows us to generate parallel algorithms for these structures?

For an array processing algorithm, a common technique used at the processor level is the copy-scan technique. This technique involves copying rows of data from one processor to another in a log(n) fashion until all processors have their own copy of that row. From there, you could perform a reduction technique to generate a sum of all the data, all while working in a parallel fashion. Take the following grid:[[#References|[1]]]

The basic process for copy-scan would be to:
Step 1) Copy the row 1 array to row 2.
Step 2) Copy the row 1 array to row 3, row 2 to row 4, etc on the next run.
Step 3) Continue in this manner until all rows have been copied in a log(n) fashion.
Step 4) Perform the parallel operations to generate the desired result (reduction for sum, etc.).

[[File:CopyScan.gif]]

But how does this same process work in the linked list world?

With linked lists, there is a concept called pointer doubling, which works in a very similar manner to copy-scan.[[#References|[1]]]

Step 1) Each processor will make a copy of the pointer it holds to its neighbor.
Step 2) Next, each processor will make a pointer to the processor 2 steps away.
Step 3) This continues in logarithmic fashion until each processor has a pointer to the end of the chain.
Step 4) Perform the parallel operations to generate the desired result.

One of the uses for pointer doubling is to perform partial sums of a linked list. The way that this is accomplished is by adding the value held by the node with the value stored in the node it is pointing to. This is repeated until all pointers have reached the end of the list. The result is a linked list which contains the sum of the node and all preceding nodes. Below shows and example of this operation in action.

[[File:PartialSums1.png]]

[[File:PartialSums2.png]]

[[File:PartialSums3.png]]

[[File:PartialSums4.png]]

However, with linked list programming, similar to array-based programming, it becomes imperative to have some sort of locking mechanism or other parallel technique for [http://en.wikipedia.org/wiki/Critical_section critical sections] in order to avoid [http://en.wikipedia.org/wiki/Race_condition race conditions]. To make sure the results are correct, it is important that operations can be serialized appropriately and that data remains current and synchronized.

In this chapter, we will explore 3 linked-list based data structures and the parallelization opportunities as well as the concurrency issues they present: hash tables, trees, and graphs.

== Trees ==

=== Tree Intro ===

A tree data structure [[#References|[2]]] contains a set of ordered nodes with one parent node followed by zero or more child nodes. Typically this tree structure is used with searching or sorting algorithms to achieve log(n) efficiencies. Assuming you have a balanced tree, or a relatively equal set of nodes under each branching structure of the tree, and assuming a proper ordering structure, searches/inserts/deletes should occur far more quickly than having to traverse an entire list.

=== Opportunities for Parallelization ===

One potential slowdown in a tree data structure could occur during the traversal process. Even though search/update/insert can occur in a logarithmic fashion, traversal operations such as in-order, pre-order, post-order traversals can still require a full sequence of the list to generate all output. This gives an opportunity to generate parallel code by having various portions of the traversal occur on different processors.

=== Serial Code Example ===

Below is a code[[#References|[8]]] for serial tree traversal algorithms
with behavior as the figure below shows:

[[File: tree.PNG]]

procedure Tree_Traversal is
type Node;
type Node_Access is access Node;
type Node is record
Left : Node_Access := null;
Right : Node_Access := null;
Data : Integer;
end record;

procedure Destroy_Tree(N : in out Node_Access) is
procedure free is new Ada.Unchecked_Deallocation(Node, Node_Access);
begin
if N.Left /= null then
Destroy_Tree(N.Left);
end if;
if N.Right /= null then
Destroy_Tree(N.Right);
end if;
Free(N);
end Destroy_Tree;

function Tree(Value : Integer; Left : Node_Access; Right : Node_Access) return Node_Access is
Temp : Node_Access := new Node;
begin
Temp.Data := Value;
Temp.Left := Left;
Temp.Right := Right;
return Temp;
end Tree;

procedure Preorder(N : Node_Access) is
begin
Put(Integer'Image(N.Data));
if N.Left /= null then
Preorder(N.Left);
end if;
if N.Right /= null then
Preorder(N.Right);
end if;
end Preorder;

procedure Inorder(N : Node_Access) is
begin
if N.Left /= null then
Inorder(N.Left);
end if;
Put(Integer'Image(N.Data));
if N.Right /= null then
Inorder(N.Right);
end if;
end Inorder;

procedure Postorder(N : Node_Access) is
begin
if N.Left /= null then
Postorder(N.Left);
end if;
if N.Right /= null then
Postorder(N.Right);
end if;
Put(Integer'Image(N.Data));
end Postorder;

procedure Levelorder(N : Node_Access) is
package Queues is new Ada.Containers.Doubly_Linked_Lists(Node_Access);
use Queues;
Node_Queue : List;
Next : Node_Access;
begin
Node_Queue.Append(N);
while not Is_Empty(Node_Queue) loop
Next := First_Element(Node_Queue);
Delete_First(Node_Queue);
Put(Integer'Image(Next.Data));
if Next.Left /= null then
Node_Queue.Append(Next.Left);
end if;
if Next.Right /= null then
Node_Queue.Append(Next.Right);
end if;
end loop;
end Levelorder;

N : Node_Access;
begin
N := Tree(1,
Tree(2,
Tree(4,
Tree(7, null, null),
null),
Tree(5, null, null)),
Tree(3,
Tree(6,
Tree(8, null, null),
Tree(9, null, null)),
null));

Put("preorder: ");
Preorder(N);
New_Line;
Put("inorder: ");
Inorder(N);
New_Line;
Put("postorder: ");
Postorder(N);
New_Line;
Put("level order: ");
Levelorder(N);
New_Line;
Destroy_Tree(N);
end Tree_traversal;

=== Parallel Solution ===
[[#References|[21]]]
In many ways, a tree is the perfect candidate for parallelism. In a tree, each
node/subtree is independent. As a result, we can split up a large tree into 2, 4, 8, or
more subtrees and hold subtree on each processor. Then, the only duplicated data
that must be kept on all processors is the tiny tip of the tree that is the parent of all
of the individual subtrees. Mathematically speaking, for a tree divided among n
processors (where n is a power of two), the processors only need to hold n – 1 nodes
in common – no matter how big the tree itself is.
The fact that trees are comprised of independent sub-trees makes parallelizing them
very easy. Properly done, the portion of these traversals that is parallelizable grows
at 2n for an n-generation tree, while the processors only need to synchronize once, at
the end, so it approaches 100% for large trees (but keep in mind [http://en.wikipedia.org/wiki/Amdahl's_law Amdahl’s Law],
footnote 1). The basic steps for parallelizing these traversals are as follows:

1. Perform the traversal on the parent part of the tree.
2. Whenever you get to a node that is only present on one processor, ask that processor to execute the appropriate C algorithm detailed above.
3. The processor will return its result that can be used exactly as if it was a serial processor.

[[File:parallel_tree.png]][[#References|[18]]]

A [http://www.cs.bu.edu/teaching/c/tree/breadth-first/ Breadth-First traversal] is somewhat more complicated to implement as a
parallel system because at each level, it must access nodes from all of the parallel
processors. Theoretically, a Breadth-First traversal can achieve the same 100%
speedup of Pre-, In-, and Post-Order traversals. However, the amount of processor to
processor data transmission adds in a greater potential for delays, thus slowing
down the algorithm. Nevertheless, as the size of the tree increases the size of the
generations grows at the rate of 2n while the number of synchronizations grows at a
rate of n for an n-generation tree, so the parallelizable portion of these traversals
also approaches 100%. The basic steps for parallelizing this traversal are as
follows:

1. Perform the traversal on the parent part of the tree.
2. Whenever you get to a node that is only present on one processor, ask that processor to execute the Breadth-First C algorithm detailed above,
but wait after it finishes one generation.
3. Combine all the one-generation results from the different processors in the correct order.
4. Allow each processor to execute the next generation of the Breadth-First C algorithm detailed above, and then wait again.
5. Repeat Steps 3 and 4 until there are no nodes remaining
[[#References|[18]]]

Here, since each processor is assigned an independent sub-tree, elaborate locks are not required.

Algorithm GEN-COMP-NEXT for Parallel Tree Traversal:
for all Pi, 1<=i<=n, do
parallel begin
Step 1: Processor Pi builds the jth field of i's parent node if i is the jth child of its parent.
The jth field (if it is not the last field) is stored in the ith index of array SUPERNODE.
Step 2: Processor Pi builds node i's last fiend whose array index is (n+1)
parallel end

To obtain the required tree-traversals, the following rules are operated on the linked list produced by algorithm GEN-COMP-NEXT:
pre-order traversal: select the first copy of each node;
post-order traversal: select the last copy of each node;
in-order traversal: delete the first copy of each node if it is not a leaf and delete the last copy of each node if it has more than one child.
This linked list can be locked while editing as per the LDS chapter in Solihin book. Either a Global lock approach, Fine Grained approach or [http://en.wikipedia.org/wiki/Readers%E2%80%93writer_lock Read-Write Locks] can be used.
In this fashion we have broken up the linked list of the tree into successive parts and imposed a divide-and-conquer technique to complete the traversal.

== Hash Tables ==
'''Hash Table Intro '''

Hash tables[[#References|[4]]] are very efficient data structures often used in searching algorithms for fast lookup operations. They are used extensively in data processing as in involves a vast amount of data through the hash table using as few indirection's in the storage structure as possible.

A single hash table level look can easily become a bottleneck, thus several method were developed to overcome this difficulty. Hash tables contain a series of "buckets" that function like indexes into an array, each of which can be accessed directly using their key value. The bucket for which a piece of data will be placed is determine by a special hashing function.

The major advantage of a hash table is that lookup times are essentially a constant value, much like an array with a known index. With a proper hashing function in place, it should be fairly rare that any 2 keys would generate the same value.

In the case that 2 keys do map to the same position, there is a conflict that must be dealt with in some fashion to obtain the correct value. One way that is relevant to linked list structures is to have a chained hash table in which a linked list is created with all values that have been placed in that particular bucket. The developer would have to not only take into account the proper bucket for the data being searched for, but also must considered the chained linked list. [[#References|[7]]]

There are several parallel implementations of hash tables available that use lock based synchronization. Larson et al. use two lock levels, there is one global table level lock, and there is one separate lightweight lock (a flag) for each bucket. The high level lock is just used for setting the bucket level flags and released right afterwards. This ensures a fine grained mutual exclusion (concurrent operations on bucket level), but needs only one real lock for the implementation.

A scalable hash table for shared memory multi-processor (SMP) supports very high rates of concurrent operations (e.g., insert, delete,
and lookup), while simultaneously reducing cache misses. The SMP system has a memory subsystem and a processor subsystem interconnected
via a bus structure.

The hash table is stored in the memory subsystem to facilitate access to data items. The hash table is segmented into multiple buckets,
with each bucket containing a reference to a linked list of bucket nodes that hold references to data items with keys that hash to a common value. Individual bucket nodes contain multiple signature-pointer pairs that reference corresponding data items.
Each signature-pointer pair has a hash signature computed from a key of the data item and a pointer to the data item. The first bucket
node in the linked list for each of the buckets is stored in the hash table.

To enable multithread access, while serializing operation of the table, the SMP system utilizes two levels of locks: a table lock and
multiple bucket locks. The table lock allows access by a single processing thread to the table while blocking access for other processing
threads. The table lock is held just long enough for the thread to acquire the bucket lock of a particular bucket node. Once the table lock
is released, another thread can access the hash table and any one of the other buckets.

[[File:315px-Hash table 3 1 1 0 1 0 0 SP.svg.png]]

=== Opportunities for Parallelization ===

Hash tables can be very well suited to parallel applications. For example, system code responsible for caching between multiple processors could itself be an ideal opportunity for a shared hashmap. Each processor sharing one common cache would be able to access the relevant information all in one location.

This would, however, involve a good bit of synchronization, as each processor would need to wait in case a lock was being placed on a specific bucket in the cache hashmap. Unfortunately, traditional locking would be a bad solution to this problem as processors need to run very quickly. Having to wait for locks would destroy the application processing time. The need for a non-locking solution is critical to performance.

In Java, the standard class utilized for hashing is the HashMap[[#References|[17]]] class. This class has a fundamental weakness though in that the entire map requires synchronization prior to each access. This causes a lot of contention and many bottlenecks on a parallel machine.

Below, I will present a Java-based solution to this problem by using a ConcurrentHashMap class. This class only requires a portion of the map to be locked and reads can generally occur with no locking whatsoever.

=== HashMap Code with Locking ===

''' Simple synchronized example to increment a counter.'''[[#References|[9]]]
private Map<String,Integer> queryCounts = new HashMap<String,Integer>(1000);
private '''synchronized''' void incrementCount(String q) {
Integer cnt = queryCounts.get(q);
if (cnt == null) {
queryCounts.put(q, 1);
} else {
queryCounts.put(q, cnt + 1);
}
}

The above code was written using an ordinary HashMap data structure. Notice that we use the synchronized keyword here to signify that only one thread can enter this function at any one point in time. With a really large number of threads, however, waiting to enter the synchronized operation could be a major bottleneck.

''' Iterator example for synchronized HashMap.'''

Map m = Collections.synchronizedMap(new HashMap());
Set s = m.keySet(); // set of keys in hashmap
synchronized(m) { // synchronizing on map
Iterator i = s.iterator(); // Must be in synchronized block
while (i.hasNext())
foo(i.next());
}

In the above example, we show how an iterator could be used to traverse over a map. In this case, we would need to utilize the synchronizedMap function available in the Collections interface. Also, as you may notice, once the iterator code begins we must actually synchronize on the entire map in order to iterate through the results. But what if several processors wish to iterate through at the same time?

=== Parallel Code Solution ===

The key issue in a hash table in a parallel environment is to make sure any update/insert/delete sequences have been completed properly prior to attempting subsequent operations to make sure the data has been synched appropriately. However, since access speed is such a critical component of the design of a hash table, it is essential to try and avoid using too many locks for performing synchronization. Fortunately, a number of lock-free hash designs have been implemented to avoid this bottleneck.

One such example in Java is the ConcurrentHashMap[[#References|[9]]], which acts as a synchronized version of the [http://docs.oracle.com/javase/6/docs/api/java/util/HashMap.html HashMap]. With this structure, there is full concurrency of retrievals and adjustable expected concurrency for updates. There is, however, no locking in this data structure and retrievals will typically run in parallel along with updates/deletes. Retrievals, however, will receive all most recently completed transactions even if it cannot get the values that haven't finished being updated. This both allows for efficiency and greater concurrency.

'''Parallel Counter Increment Alternative:'''

private ConcurrentMap<String,Integer> queryCounts =
new ConcurrentHashMap<String,Integer>(1000);
private void incrementCount(String q) {
Integer oldVal, newVal;
do {
oldVal = queryCounts.get(q);
newVal = (oldVal == null) ? 1 : (oldVal + 1);
} while (!queryCounts.replace(q, oldVal, newVal));
}

The above code snippet represents an alternative to the serial option presented in the previous section, while also avoiding much of the locking that takes place using the synchronized functions or synchronized blocks. With ConcurrentHashMap, however, notice that we must implement some new code in order to handle the fact that a variety of inserts/updates could be running at the same time. The replace() function here acts much like a compare-and-set operation typically used with concurrent code. Basically, the value would be changed only if not equal to the previously mapped value. This is much more efficient that locking the entire function as we often do not expect unequal values.

'''Parallel Traversal Alternative:'''

Map m = new ConcurrentHashMap();
Set s = m.keySet(); // set of keys in hashmap
Iterator i = s.iterator(); // Must be in synchronized block
while (i.hasNext())
foo(i.next());

In the case of a traversal, recall that ConcurrentHashMaps require to locking on read operations. Thus we can actually remove the synchronized condition here and iterate in a normal fashion.

== Graphs ==
=== Graph Intro ===

A graph data structure[[#References|[10]]] is another type of linked-list structure that focuses on data relationships and the most efficient ways to traverse from one node to another. For example, in a networking application, one network node may have connections to a variety of other network nodes. These nodes then also link to a variety of other nodes in the network. Using this connection of nodes, it would be possible to then find a path from one specific node to another in the chain. This could be accomplished by having each node contain a linked list of pointers to all other reachable nodes.

[[File:250px-6n-graf.svg.png]]

=== Opportunities for Parallelization ===

Graphs[[#References|[10]]] consist of a finite set of ordered pairs called edges or arcs, of certain entities called nodes or vertices. From one given vertex, one would typically want to order the different paths from one vertex to another using its list of edges or, more than likely, would be interested in the fastest means of getting from one of these vertexes to some sort of destination vertex.

Graph nodes typically will keep their list of edges in a linked list. Also, when attempting to create a shortest path algorithm on the fly, the graph will typically use a combination of a linked list to represent the path as it's being built, along with a queue that is used for each step of that process. Synchronizing all of these can be a major challenge.

Much like the hash table, graphs cannot afford to be slow and must often generate results in a very efficient manner. Having to lock on each list of edges or locking on a shortest path list would really be a major obstacle.

Certainly though, the need for parallel processing becomes critical when you consider, for example, that social networking has become such a major proponent of graph algorithms. Facebook now has roughly a billion users[[#References|[15]]] and each user has series of friend links that must be analyzed and examined. This list just keeps growing and growing.

One of the most significant opportunities for a parallel algorithm with a graph data structure is with the traversal algorithms. We can use Breadth-First search[[#References|[16]]] as an example of this, starting from an initial node and expanding outwards until reaching the destination node.

=== Breadth First Search - Serial Version ===

The following shows a sample of a bread first algorithm which traverses from the city of Frankfurt to Augsburg and Stuttgart Germany. In does so, the graph begins at a root node (Frankfurt) and expands outwardly to all connected nodes on each step. From there, each of those nodes proceeds to expand the search outwards until all nodes have been covered.

[[File:GermanyBFS.png]][[#References|[13]]]

The following code snippet implements a BFS search function. This function utilized coloring schemes and marks to denote that a node has been visited. It begins with an initial vertex in a queue and expands outward to all its successors until no further elements remain unmarked.[[#References|[12]]]

public void search(Graph g)
{
g.paint(Color.white); // paint all the graph vertices with white
g.mark(false); // unmark the whole graph
refresh(null); // and redraw it
Vertex r = g.root(); // the root is painted grey
g.paint(r, Color.gray); refresh(g.box(r));
java.util.Vector queue = new java.util.Vector();
queue.addElement(r); // and put in a queue
while(!queue.isEmpty())
{
Vertex u = (Vertex) queue.firstElement();
queue.removeElement(u); // extract a vertex from the queue
g.mark(u, true); refresh(g.box(u));
int dp = g.degreePlus(u);
for(int i = 0; i < dp; i++) // look at its successors
{
Vertex v = g.ithSucc(i, u);
if(Color.white == g.color(v))
{
queue.addElement(v);
g.paint(v, Color.gray); refresh(g.box(v));
}
}
g.paint(u, Color.black); refresh(g.box(u));
g.mark(u, false); refresh(g.box(u));
}
}

=== Parallel Solution ===

But could we introduce parallel mechanisms into this Breadth First search? The most logical and effective way, instead of utilizing locks and synchronized regions, is to use data parallel techniques during the traversal. This can be accomplished by having each node of a given breadth search step be sent to a separate processor. So, using the above example, instead of having Frankfurt->Mannheim followed by Frankfurt->Wurzburg followed by Frankfurt->Bassel on the same processor, Frankfurt could split out all 3 searches in a parallel fashion onto 3 different processors. Then, possible some cleanup code would be left at the end to visit any remaining untouched nodes. In a network routing applications, being able to split up the search for each IP address code would make searched significantly faster that allowing one processor to be a bottleneck.

Using locking pseudocode, you might have an algorithm similar to this:

for all vertices u at level d in parallel do
for all adjacencies v of u in parallel do
dv = D[v];
if(dv < 0) // v is visited for the first time
vis = fetch_and_add(&Visited[v], 1); '''LOCK'''
if(vis == 0) // v is added to a stack only once
D[v] = d+1;
pS[count++] = v; // Add v to local thread stack
fetch_and_add(&sigma[v], sigma[u]); '''LOCK'''
fetch_and_add(&Pcount[v], 1); // Add u to predecessor list of v '''LOCK'''
if(dv == d + 1)
fetch_and_add(&sigma[v], sigma[u]); '''LOCK'''
fetch_and_add(&Pcount[v], 1); // Add u to predecessor list of v '''LOCK'''

A much better parallel algorithm is represented in the following pseudocode. Notice that each of the vertices is sent to a separate processor and send/receive operations will eventually sync up the path information.

[[File:Parallel-code.PNG]][[#References|[14]]]

The following graph also shows how now each of the regional sets of vertices being search can be added to the path in a parallel fashion.

[[File:Parallel-graph.PNG]][[#References|[11]]]

Every set of vertices in the same distance from the source is assigned to a processor. This set of vertices is called a regional set of vertices. The goal is to find the shortest path connecting each region.

= Quiz =

1. Describe the copy-scan technique.

2. Describe the pointer doubling technique.

3. Which concurrency issues are of the most concern in a tree data structure?

4. What is the alternative to using a copy-scan technique in pointer-based programming?

5. Which concurrency issues are of the most concern with hash table data structures?

6. Which concurrency issues are of the most concern with graph data structures?

7. Why would you not want locking mechanisms in hash tables?

8. What is the nature of the linked list in a tree structure?

9. Describe a parallel alternative in the tree data structure.

10. Describe a parallel alternative in a graph data structure.

= References =

#http://people.engr.ncsu.edu/efg/506/s01/lectures/notes/lec8.html
#http://en.wikipedia.org/wiki/Tree_%28data_structure%29
#http://oreilly.com/catalog/masteralgoc/chapter/ch08.pdf
#http://www.devjavasoft.org/code/classhashtable.html
#http://osr600doc.sco.com/en/SDK_c++/_Intro_graph.html
#http://web.eecs.utk.edu/~berry/cs302s02/src/code/Chap14/Graph.java
#http://en.wikipedia.org/wiki/File:Hash_table_3_1_1_0_1_0_0_SP.svg
#http://rosettacode.org/wiki/Talk:Tree_traversal
#http://www.javamex.com/tutorials/synchronization_concurrency_8_hashmap.shtml
#http://en.wikipedia.org/wiki/Graph_%28abstract_data_type%29
#http://www.cc.gatech.edu/~bader/papers/PPoPP12/PPoPP-2012-part2.pdf
#http://renaud.waldura.com/portfolio/graph-algorithms/classes/graph/BFSearch.java
#http://en.wikipedia.org/w/index.php?title=File%3AGermanyBFS.svg
#http://sc05.supercomputing.org/schedule/pdf/pap346.pdf
#http://www.facebook.com/press/info.php?statistics
#http://en.wikipedia.org/wiki/Breadth-first_search
#http://code.wikia.com/wiki/Hashmap
#http://www.shodor.org/petascale/materials/UPModules/Binary_Tree_Traversal
#http://en.wikipedia.org/wiki/Readers%E2%80%93writer_lock
#http://dl.acm.org/citation.cfm?id=320078
#http://en.wikipedia.org/wiki/Tree_traversal
P.-A. Larson, M. R. Krishnan,and G. V. Reilly, “Scaleable hash table for
shared-memory multiprocessor system,” US Patent number: 6578131,
2003
http://ww2.cs.mu.oz.au/~pjs/papers/paralleldp.pdf

File:PartialSums4.png

2014-02-26T03:24:53Z

Remcelfr:

File:PartialSums3.png

2014-02-26T03:24:46Z

Remcelfr:

File:PartialSums2.png

2014-02-26T03:24:39Z

Remcelfr:

2014-02-24T03:28:03Z

Remcelfr:

= Chapter 5a CSC/ECE 506 Spring 2013 / Other linked data structures =

Original wiki : http://wiki.expertiza.ncsu.edu/index.php/CSC/ECE_506_Spring_2013/5a_ks

= Overview =

Linked Data Structures(LDS) consists of different types of data structures such as [http://en.wikipedia.org/wiki/Linked_list linked lists], [http://en.wikibooks.org/wiki/Data_Structures/Trees trees], [http://en.wikipedia.org/wiki/Hash_table hash tables] and [http://en.wikibooks.org/wiki/Data_Structures/Graphs graphs]. Although each structure is diversed, LDS traversal shares a common characteristic in reading a node and discovering the other nodes it points to. Hence, this often introduces loop carried dependence. Chapter 5 of Solihin, discusses various algorithms on parallelizing LDS using a simple linked list. In this wiki, we attempt to cover other LDS such as trees, hashes and graphs, and how the parallelization algorithms discussed can be applied to these structures. This wiki explores concurrency problems related to each type and possible solutions for parallelizing them.

= Concurrency Problem in LDS =

Non-serializable outcomes can often occur while attempting to parallelize LDS in scenarios like :

Parallel execution of two operations that access a common node, in which at least one operation involves writing to the node,
can produce conflicts that lead to non- serializable outcome. Conflicts can occur between LDS operations and memory management
functions such as memory de-allocation and allocation.

Solihin discusses three approaches using locks to resolve these issues namely :

===Parallelization among Readers===
[[#References|[19]]]
This is achieved by ensuring [http://en.wikipedia.org/wiki/Mutual_exclusion mutual exclusion] between a read-write and a read-only operation, and not between two read-only operations. This is achieved by defining a read lock and a write lock.

'''Lock compatibility : '''
Read Lock requested Write Lock requested
Read Locked Yes No
Write Locked No No

===Global Lock Approach===
[[#References|[20]]]
A higher degree of parallelism can be obtained by maintaining a single global lock for each LDS. This however can support only 1 thread modifying a list at any given time.

===Fine-Grain Lock Approach===
[[#References|[20]]]
The Fine-Grain lock approach resolves the previous restriction of only sequentially modifying a given list by maintaining locks for each node. Hence, this is a much more tedious approach. The principle here is that, nodes that are modified must be write locked, and nodes that are being read and hence must remain valid are read locked.

In the following sections we describe the problems related to various LDS and some of their possible solutions.

= Introduction to Linked-List Parallel Programming =

One component that tends to link together various data structures is their reliance at some level on an internal pointer-based linked list. For example, hash tables have linked lists to support chained links to a given bucket in order to resolve collisions, trees have linked lists with left and right tree node paths, and graphs have linked lists to determine shortest path algorithms.

But what mechanism allows us to generate parallel algorithms for these structures?

For an array processing algorithm, a common technique used at the processor level is the copy-scan technique. This technique involves copying rows of data from one processor to another in a log(n) fashion until all processors have their own copy of that row. From there, you could perform a reduction technique to generate a sum of all the data, all while working in a parallel fashion. Take the following grid:[[#References|[1]]]

The basic process for copy-scan would be to:
Step 1) Copy the row 1 array to row 2.
Step 2) Copy the row 1 array to row 3, row 2 to row 4, etc on the next run.
Step 3) Continue in this manner until all rows have been copied in a log(n) fashion.
Step 4) Perform the parallel operations to generate the desired result (reduction for sum, etc.).

[[File:CopyScan.gif]]

But how does this same process work in the linked list world?

With linked lists, there is a concept called pointer doubling, which works in a very similar manner to copy-scan.[[#References|[1]]]

Step 1) Each processor will make a copy of the pointer it holds to it's neighbor.
Step 2) Next, each processor will make a pointer to the processor 2 steps away.
Step 3) This continues in logarithmic fashion until each processor has a pointer to the end of the chain.
Step 4) Perform the parallel operations to generate the desired result.

[[File:linkedlist.gif]]

However, with linked list programming, similar to array-based programming, it becomes imperative to have some sort of locking mechanism or other parallel technique for [http://en.wikipedia.org/wiki/Critical_section critical sections] in order to avoid [http://en.wikipedia.org/wiki/Race_condition race conditions]. To make sure the results are correct, it is important that operations can be serialized appropriately and that data remains current and synchronized.

In this chapter, we will explore 3 linked-list based data structures and the parallelization opportunities as well as the concurrency issues they present: hash tables, trees, and graphs.

== Trees ==

=== Tree Intro ===

A tree data structure [[#References|[2]]] contains a set of ordered nodes with one parent node followed by zero or more child nodes. Typically this tree structure is used with searching or sorting algorithms to achieve log(n) efficiencies. Assuming you have a balanced tree, or a relatively equal set of nodes under each branching structure of the tree, and assuming a proper ordering structure, searches/inserts/deletes should occur far more quickly than having to traverse an entire list.

=== Opportunities for Parallelization ===

One potential slowdown in a tree data structure could occur during the traversal process. Even though search/update/insert can occur in a logarithmic fashion, traversal operations such as in-order, pre-order, post-order traversals can still require a full sequence of the list to generate all output. This gives an opportunity to generate parallel code by having various portions of the traversal occur on different processors.

=== Serial Code Example ===

Below is a code[[#References|[8]]] for serial tree traversal algorithms
with behavior as the figure below shows:

[[File: tree.PNG]]

procedure Tree_Traversal is
type Node;
type Node_Access is access Node;
type Node is record
Left : Node_Access := null;
Right : Node_Access := null;
Data : Integer;
end record;

procedure Destroy_Tree(N : in out Node_Access) is
procedure free is new Ada.Unchecked_Deallocation(Node, Node_Access);
begin
if N.Left /= null then
Destroy_Tree(N.Left);
end if;
if N.Right /= null then
Destroy_Tree(N.Right);
end if;
Free(N);
end Destroy_Tree;

function Tree(Value : Integer; Left : Node_Access; Right : Node_Access) return Node_Access is
Temp : Node_Access := new Node;
begin
Temp.Data := Value;
Temp.Left := Left;
Temp.Right := Right;
return Temp;
end Tree;

procedure Preorder(N : Node_Access) is
begin
Put(Integer'Image(N.Data));
if N.Left /= null then
Preorder(N.Left);
end if;
if N.Right /= null then
Preorder(N.Right);
end if;
end Preorder;

procedure Inorder(N : Node_Access) is
begin
if N.Left /= null then
Inorder(N.Left);
end if;
Put(Integer'Image(N.Data));
if N.Right /= null then
Inorder(N.Right);
end if;
end Inorder;

procedure Postorder(N : Node_Access) is
begin
if N.Left /= null then
Postorder(N.Left);
end if;
if N.Right /= null then
Postorder(N.Right);
end if;
Put(Integer'Image(N.Data));
end Postorder;

procedure Levelorder(N : Node_Access) is
package Queues is new Ada.Containers.Doubly_Linked_Lists(Node_Access);
use Queues;
Node_Queue : List;
Next : Node_Access;
begin
Node_Queue.Append(N);
while not Is_Empty(Node_Queue) loop
Next := First_Element(Node_Queue);
Delete_First(Node_Queue);
Put(Integer'Image(Next.Data));
if Next.Left /= null then
Node_Queue.Append(Next.Left);
end if;
if Next.Right /= null then
Node_Queue.Append(Next.Right);
end if;
end loop;
end Levelorder;

N : Node_Access;
begin
N := Tree(1,
Tree(2,
Tree(4,
Tree(7, null, null),
null),
Tree(5, null, null)),
Tree(3,
Tree(6,
Tree(8, null, null),
Tree(9, null, null)),
null));

Put("preorder: ");
Preorder(N);
New_Line;
Put("inorder: ");
Inorder(N);
New_Line;
Put("postorder: ");
Postorder(N);
New_Line;
Put("level order: ");
Levelorder(N);
New_Line;
Destroy_Tree(N);
end Tree_traversal;

=== Parallel Solution ===
[[#References|[21]]]
In many ways, a tree is the perfect candidate for parallelism. In a tree, each
node/subtree is independent. As a result, we can split up a large tree into 2, 4, 8, or
more subtrees and hold subtree on each processor. Then, the only duplicated data
that must be kept on all processors is the tiny tip of the tree that is the parent of all
of the individual subtrees. Mathematically speaking, for a tree divided among n
processors (where n is a power of two), the processors only need to hold n – 1 nodes
in common – no matter how big the tree itself is.
The fact that trees are comprised of independent sub-trees makes parallelizing them
very easy. Properly done, the portion of these traversals that is parallelizable grows
at 2n for an n-generation tree, while the processors only need to synchronize once, at
the end, so it approaches 100% for large trees (but keep in mind [http://en.wikipedia.org/wiki/Amdahl's_law Amdahl’s Law],
footnote 1). The basic steps for parallelizing these traversals are as follows:

1. Perform the traversal on the parent part of the tree.
2. Whenever you get to a node that is only present on one processor, ask that processor to execute the appropriate C algorithm detailed above.
3. The processor will return its result that can be used exactly as if it was a serial processor.

[[File:parallel_tree.png]][[#References|[18]]]

A [http://www.cs.bu.edu/teaching/c/tree/breadth-first/ Breadth-First traversal] is somewhat more complicated to implement as a
parallel system because at each level, it must access nodes from all of the parallel
processors. Theoretically, a Breadth-First traversal can achieve the same 100%
speedup of Pre-, In-, and Post-Order traversals. However, the amount of processor to
processor data transmission adds in a greater potential for delays, thus slowing
down the algorithm. Nevertheless, as the size of the tree increases the size of the
generations grows at the rate of 2n while the number of synchronizations grows at a
rate of n for an n-generation tree, so the parallelizable portion of these traversals
also approaches 100%. The basic steps for parallelizing this traversal are as
follows:

1. Perform the traversal on the parent part of the tree.
2. Whenever you get to a node that is only present on one processor, ask that processor to execute the Breadth-First C algorithm detailed above,
but wait after it finishes one generation.
3. Combine all the one-generation results from the different processors in the correct order.
4. Allow each processor to execute the next generation of the Breadth-First C algorithm detailed above, and then wait again.
5. Repeat Steps 3 and 4 until there are no nodes remaining
[[#References|[18]]]

Here, since each processor is assigned an independent sub-tree, elaborate locks are not required.

Algorithm GEN-COMP-NEXT for Parallel Tree Traversal:
for all Pi, 1<=i<=n, do
parallel begin
Step 1: Processor Pi builds the jth field of i's parent node if i is the jth child of its parent.
The jth field (if it is not the last field) is stored in the ith index of array SUPERNODE.
Step 2: Processor Pi builds node i's last fiend whose array index is (n+1)
parallel end

To obtain the required tree-traversals, the following rules are operated on the linked list produced by algorithm GEN-COMP-NEXT:
pre-order traversal: select the first copy of each node;
post-order traversal: select the last copy of each node;
in-order traversal: delete the first copy of each node if it is not a leaf and delete the last copy of each node if it has more than one child.
This linked list can be locked while editing as per the LDS chapter in Solihin book. Either a Global lock approach, Fine Grained approach or [http://en.wikipedia.org/wiki/Readers%E2%80%93writer_lock Read-Write Locks] can be used.
In this fashion we have broken up the linked list of the tree into successive parts and imposed a divide-and-conquer technique to complete the traversal.

== Hash Tables ==
'''Hash Table Intro '''

Hash tables[[#References|[4]]] are very efficient data structures often used in searching algorithms for fast lookup operations. They are used extensively in data processing as in involves a vast amount of data through the hash table using as few indirection's in the storage structure as possible.

A single hash table level look can easily become a bottleneck, thus several method were developed to overcome this difficulty. Hash tables contain a series of "buckets" that function like indexes into an array, each of which can be accessed directly using their key value. The bucket for which a piece of data will be placed is determine by a special hashing function.

The major advantage of a hash table is that lookup times are essentially a constant value, much like an array with a known index. With a proper hashing function in place, it should be fairly rare that any 2 keys would generate the same value.

In the case that 2 keys do map to the same position, there is a conflict that must be dealt with in some fashion to obtain the correct value. One way that is relevant to linked list structures is to have a chained hash table in which a linked list is created with all values that have been placed in that particular bucket. The developer would have to not only take into account the proper bucket for the data being searched for, but also must considered the chained linked list. [[#References|[7]]]

There are several parallel implementations of hash tables available that use lock based synchronization. Larson et al. use two lock levels, there is one global table level lock, and there is one separate lightweight lock (a flag) for each bucket. The high level lock is just used for setting the bucket level flags and released right afterwards. This ensures a fine grained mutual exclusion (concurrent operations on bucket level), but needs only one real lock for the implementation.

A scalable hash table for shared memory multi-processor (SMP) supports very high rates of concurrent operations (e.g., insert, delete,
and lookup), while simultaneously reducing cache misses. The SMP system has a memory subsystem and a processor subsystem interconnected
via a bus structure.

The hash table is stored in the memory subsystem to facilitate access to data items. The hash table is segmented into multiple buckets,
with each bucket containing a reference to a linked list of bucket nodes that hold references to data items with keys that hash to a common value. Individual bucket nodes contain multiple signature-pointer pairs that reference corresponding data items.
Each signature-pointer pair has a hash signature computed from a key of the data item and a pointer to the data item. The first bucket
node in the linked list for each of the buckets is stored in the hash table.

To enable multithread access, while serializing operation of the table, the SMP system utilizes two levels of locks: a table lock and
multiple bucket locks. The table lock allows access by a single processing thread to the table while blocking access for other processing
threads. The table lock is held just long enough for the thread to acquire the bucket lock of a particular bucket node. Once the table lock
is released, another thread can access the hash table and any one of the other buckets.

[[File:315px-Hash table 3 1 1 0 1 0 0 SP.svg.png]]

=== Opportunities for Parallelization ===

Hash tables can be very well suited to parallel applications. For example, system code responsible for caching between multiple processors could itself be an ideal opportunity for a shared hashmap. Each processor sharing one common cache would be able to access the relevant information all in one location.

This would, however, involve a good bit of synchronization, as each processor would need to wait in case a lock was being placed on a specific bucket in the cache hashmap. Unfortunately, traditional locking would be a bad solution to this problem as processors need to run very quickly. Having to wait for locks would destroy the application processing time. The need for a non-locking solution is critical to performance.

In Java, the standard class utilized for hashing is the HashMap[[#References|[17]]] class. This class has a fundamental weakness though in that the entire map requires synchronization prior to each access. This causes a lot of contention and many bottlenecks on a parallel machine.

Below, I will present a Java-based solution to this problem by using a ConcurrentHashMap class. This class only requires a portion of the map to be locked and reads can generally occur with no locking whatsoever.

=== HashMap Code with Locking ===

''' Simple synchronized example to increment a counter.'''[[#References|[9]]]
private Map<String,Integer> queryCounts = new HashMap<String,Integer>(1000);
private '''synchronized''' void incrementCount(String q) {
Integer cnt = queryCounts.get(q);
if (cnt == null) {
queryCounts.put(q, 1);
} else {
queryCounts.put(q, cnt + 1);
}
}

The above code was written using an ordinary HashMap data structure. Notice that we use the synchronized keyword here to signify that only one thread can enter this function at any one point in time. With a really large number of threads, however, waiting to enter the synchronized operation could be a major bottleneck.

''' Iterator example for synchronized HashMap.'''

Map m = Collections.synchronizedMap(new HashMap());
Set s = m.keySet(); // set of keys in hashmap
synchronized(m) { // synchronizing on map
Iterator i = s.iterator(); // Must be in synchronized block
while (i.hasNext())
foo(i.next());
}

In the above example, we show how an iterator could be used to traverse over a map. In this case, we would need to utilize the synchronizedMap function available in the Collections interface. Also, as you may notice, once the iterator code begins we must actually synchronize on the entire map in order to iterate through the results. But what if several processors wish to iterate through at the same time?

=== Parallel Code Solution ===

The key issue in a hash table in a parallel environment is to make sure any update/insert/delete sequences have been completed properly prior to attempting subsequent operations to make sure the data has been synched appropriately. However, since access speed is such a critical component of the design of a hash table, it is essential to try and avoid using too many locks for performing synchronization. Fortunately, a number of lock-free hash designs have been implemented to avoid this bottleneck.

One such example in Java is the ConcurrentHashMap[[#References|[9]]], which acts as a synchronized version of the [http://docs.oracle.com/javase/6/docs/api/java/util/HashMap.html HashMap]. With this structure, there is full concurrency of retrievals and adjustable expected concurrency for updates. There is, however, no locking in this data structure and retrievals will typically run in parallel along with updates/deletes. Retrievals, however, will receive all most recently completed transactions even if it cannot get the values that haven't finished being updated. This both allows for efficiency and greater concurrency.

'''Parallel Counter Increment Alternative:'''

private ConcurrentMap<String,Integer> queryCounts =
new ConcurrentHashMap<String,Integer>(1000);
private void incrementCount(String q) {
Integer oldVal, newVal;
do {
oldVal = queryCounts.get(q);
newVal = (oldVal == null) ? 1 : (oldVal + 1);
} while (!queryCounts.replace(q, oldVal, newVal));
}

The above code snippet represents an alternative to the serial option presented in the previous section, while also avoiding much of the locking that takes place using the synchronized functions or synchronized blocks. With ConcurrentHashMap, however, notice that we must implement some new code in order to handle the fact that a variety of inserts/updates could be running at the same time. The replace() function here acts much like a compare-and-set operation typically used with concurrent code. Basically, the value would be changed only if not equal to the previously mapped value. This is much more efficient that locking the entire function as we often do not expect unequal values.

'''Parallel Traversal Alternative:'''

Map m = new ConcurrentHashMap();
Set s = m.keySet(); // set of keys in hashmap
Iterator i = s.iterator(); // Must be in synchronized block
while (i.hasNext())
foo(i.next());

In the case of a traversal, recall that ConcurrentHashMaps require to locking on read operations. Thus we can actually remove the synchronized condition here and iterate in a normal fashion.

== Graphs ==
=== Graph Intro ===

A graph data structure[[#References|[10]]] is another type of linked-list structure that focuses on data relationships and the most efficient ways to traverse from one node to another. For example, in a networking application, one network node may have connections to a variety of other network nodes. These nodes then also link to a variety of other nodes in the network. Using this connection of nodes, it would be possible to then find a path from one specific node to another in the chain. This could be accomplished by having each node contain a linked list of pointers to all other reachable nodes.

[[File:250px-6n-graf.svg.png]]

=== Opportunities for Parallelization ===

Graphs[[#References|[10]]] consist of a finite set of ordered pairs called edges or arcs, of certain entities called nodes or vertices. From one given vertex, one would typically want to order the different paths from one vertex to another using it's list of edges or, more than likely, would be interested in the fastest means of getting from one of these vertexes to some sort of destination vertex.

Graph nodes typically will keep their list of edges in a linked list. Also, when attempting to create a shortest path algorithm on the fly, the graph will typically use a combination of a linked list to represent the path as it's being built, along with a queue that is used for each step of that process. Synchronizing all of these can be a major challenge.

Much like the hash table, graphs cannot afford to be slow and must often generate results in a very efficient manner. Having to lock on each list of edges or locking on a shortest path list would really be a major obstacle.

Certainly though, the need for parallel processing becomes critical when you consider, for example, that social networking has become such a major proponent of graph algorithms. Facebook now has roughly a billion users[[#References|[15]]] and each user has series of friend links that must be analyzed and examined. This list just keeps growing and growing.

One of the most significant opportunities for a parallel algorithm with a graph data structure is with the traversal algorithms. We can use Breadth-First search[[#References|[16]]] as an example of this, starting from an initial node and expanding outwards until reaching the destination node.

=== Breadth First Search - Serial Version ===

The following shows a sample of a bread first algorithm which traverses from the city of Frankfurt to Augsburg and Stuttgart Germany. In does so, the graph begins at a root node (Frankfurt) and expands outwardly to all connected nodes on each step. From there, each of those nodes proceeds to expand the search outwards until all nodes have been covered.

[[File:GermanyBFS.png]][[#References|[13]]]

The following code snippet implements a BFS search function. This function utilized coloring schemes and marks to denote that a node has been visited. It begins with an initial vertex in a queue and expands outward to all it's successors until no further elements remain unmarked.[[#References|[12]]]

public void search (Graph g)
{
g.paint(Color.white); // paint all the graph vertices with white
g.mark(false); // unmark the whole graph
refresh(null); // and redraw it
Vertex r = g.root(); // the root is painted grey
g.paint(r, Color.gray); refresh(g.box(r));
java.util.Vector queue = new java.util.Vector();
queue.addElement(r); // and put in a queue
while (!queue.isEmpty())
{
Vertex u = (Vertex) queue.firstElement();
queue.removeElement(u); // extract a vertex from the queue
g.mark(u, true); refresh(g.box(u));
int dp = g.degreePlus(u);
for (int i = 0; i < dp; i++) // look at its successors
{
Vertex v = g.ithSucc(i, u);
if (Color.white == g.color(v))
{
queue.addElement(v);
g.paint(v, Color.gray); refresh(g.box(v));
}
}
g.paint(u, Color.black); refresh(g.box(u));
g.mark(u, false); refresh(g.box(u));
}
}

=== Parallel Solution ===

But could we introduce parallel mechanisms into this Breadth First search? The most logical and effective way, instead of utilizing locks and synchronized regions, is to use data parallel techniques during the traversal. This can be accomplished by having each node of a given breadth search step be sent to a separate processor. So, using the above example, instead of having Frankfurt->Mannheim followed by Frankfurt->Wurzburg followed by Frankfurt->Bassel on the same processor, Frankfurt could split out all 3 searches in a parallel fashion onto 3 different processors. Then, possible some cleanup code would be left at the end to visit any remaining untouched nodes. In a network routing applications, being able to split up the search for each IP address code would make searched significantly faster that allowing one processor to be a bottleneck.

Using locking pseudocode, you might have an algorithm similar to this:

for all vertices u at level d in parallel do
for all adjacencies v of u in parallel do
dv = D[v];
if (dv < 0) // v is visited for the first time
vis = fetch_and_add(&Visited[v], 1); '''LOCK'''
if (vis == 0) // v is added to a stack only once
D[v] = d+1;
pS[count++] = v; // Add v to local thread stack
fetch_and_add(&sigma[v], sigma[u]); '''LOCK'''
fetch_and_add(&Pcount[v], 1); // Add u to predecessor list of v '''LOCK'''
if (dv == d + 1)
fetch_and_add(&sigma[v], sigma[u]); '''LOCK'''
fetch_and_add(&Pcount[v], 1); // Add u to predecessor list of v '''LOCK'''

A much better parallel algorithm is represented in the following pseudocode. Notice that each of the vertices is sent to a separate processor and send/receive operations will eventually sync up the path information.

[[File:Parallel-code.PNG]][[#References|[14]]]

The following graph also shows how now each of the regional sets of vertices being search can be added to the path in a parallel fashion.

[[File:Parallel-graph.PNG]][[#References|[11]]]

Every set of vertices in the same distance from the source is assigned to a processor. This set of vertices is called a regional set of vertices. The goal is to find the shortest path connecting each region.

= Quiz =

1. Describe the copy-scan technique.

2. Describe the pointer doubling technique.

3. Which concurrency issues are of the most concern in a tree data structure?

4. What is the alternative to using a copy-scan technique in pointer-based programming?

5. Which concurrency issues are of the most concern with hash table data structures?

6. Which concurrency issues are of the most concern with graph data structures?

7. Why would you not want locking mechanisms in hash tables?

8. What is the nature of the linked list in a tree structure?

9. Describe a parallel alternative in the tree data structure.

10. Describe a parallel alternative in a graph data structure.

= References =

#http://people.engr.ncsu.edu/efg/506/s01/lectures/notes/lec8.html
#http://en.wikipedia.org/wiki/Tree_%28data_structure%29
#http://oreilly.com/catalog/masteralgoc/chapter/ch08.pdf
#http://www.devjavasoft.org/code/classhashtable.html
#http://osr600doc.sco.com/en/SDK_c++/_Intro_graph.html
#http://web.eecs.utk.edu/~berry/cs302s02/src/code/Chap14/Graph.java
#http://en.wikipedia.org/wiki/File:Hash_table_3_1_1_0_1_0_0_SP.svg
#http://rosettacode.org/wiki/Talk:Tree_traversal
#http://www.javamex.com/tutorials/synchronization_concurrency_8_hashmap.shtml
#http://en.wikipedia.org/wiki/Graph_%28abstract_data_type%29
#http://www.cc.gatech.edu/~bader/papers/PPoPP12/PPoPP-2012-part2.pdf
#http://renaud.waldura.com/portfolio/graph-algorithms/classes/graph/BFSearch.java
#http://en.wikipedia.org/w/index.php?title=File%3AGermanyBFS.svg
#http://sc05.supercomputing.org/schedule/pdf/pap346.pdf
#http://www.facebook.com/press/info.php?statistics
#http://en.wikipedia.org/wiki/Breadth-first_search
#http://code.wikia.com/wiki/Hashmap
#http://www.shodor.org/petascale/materials/UPModules/Binary_Tree_Traversal
#http://en.wikipedia.org/wiki/Readers%E2%80%93writer_lock
#http://dl.acm.org/citation.cfm?id=320078
#http://en.wikipedia.org/wiki/Tree_traversal
P.-A. Larson, M. R. Krishnan,and G. V. Reilly, “Scaleable hash table for
shared-memory multiprocessor system,” US Patent number: 6578131,
2003
http://ww2.cs.mu.oz.au/~pjs/papers/paralleldp.pdf