{"id":{"repo_id":"denver","oai_identifier":"oai:digitalcommons.du.edu:etd-1755"},"canonical_url":"https://search.ndltd.org/etd/denver/oai:digitalcommons.du.edu:etd-1755","repository":{"repo_id":"denver","name":"University of Denver","base_url":"https://digitalcommons.du.edu/do/oai/"},"display":{"title":"Memory Access Patterns for Cellular Automata Using GPGPUs","abstract":"Today's graphical processing units have hundreds of individual processing cores that can be used for general purpose computation of mathematical and scientific problems. Due to their hardware architecture, these devices are especially effective when solving problems that exhibit a high degree of spatial locality. Cellular automata use small, local neighborhoods to determine successive states of individual elements and therefore, provide an excellent opportunity for the application of general purpose GPU computing. However, the GPU presents a challenging environment because it lacks many of the features of traditional CPUs, such as automatic, on-chip caching of data. To fully realize the potential of a GPU, specialized memory techniques and patterns must be employed to account for their unique architecture. Several techniques are presented which not only dramatically improve performance, but, in many cases, also simplify implementation. Many of the approaches discussed relate to the organization of data in memory or patterns for accessing that data, while others detail methods of increasing the computation to memory access ratio. The ideas presented are generic, and applicable to cellular automata models as a whole. Example implementations are given for several problems, including the Game of Life and Gaussian blurring, while performance characteristics, such as instruction and memory accesses counts, are analyzed and compared. A case study is detailed, showing the effectiveness of the various techniques when applied to a larger, real-world problem. Lastly, the reasoning behind each of the improvements is explained, providing general guidelines for determining when a given technique will be most and least effective.","abstract_html":"Today&#x27;s graphical processing units have hundreds of individual processing cores that can be used for general purpose computation of mathematical and scientific problems. Due to their hardware architecture, these devices are especially effective when solving problems that exhibit a high degree of spatial locality. Cellular automata use small, local neighborhoods to determine successive states of individual elements and therefore, provide an excellent opportunity for the application of general purpose GPU computing. However, the GPU presents a challenging environment because it lacks many of the features of traditional CPUs, such as automatic, on-chip caching of data. To fully realize the potential of a GPU, specialized memory techniques and patterns must be employed to account for their unique architecture. Several techniques are presented which not only dramatically improve performance, but, in many cases, also simplify implementation. Many of the approaches discussed relate to the organization of data in memory or patterns for accessing that data, while others detail methods of increasing the computation to memory access ratio. The ideas presented are generic, and applicable to cellular automata models as a whole. Example implementations are given for several problems, including the Game of Life and Gaussian blurring, while performance characteristics, such as instruction and memory accesses counts, are analyzed and compared. A case study is detailed, showing the effectiveness of the various techniques when applied to a larger, real-world problem. Lastly, the reasoning behind each of the improvements is explained, providing general guidelines for determining when a given technique will be most and least effective.","abstract_has_math":false,"creators":["Balasalle, James Michael"],"institution":null,"degree_name":"M.S.","degree_level":"Masters Thesis","degree_discipline":null,"degree_department":null,"school":null,"contributors":["Matthew J. Rutherford, Ph.D.","Mario Lopez","Mohammad H. Mahoor"],"advisors":[],"committee_chairs":[],"committee_members":[],"year":null,"date_issued":"","date_published":null,"updated_at":"2026-11-19T07:54:02Z","subjects":["Cellular automata","Compute Unified Device Architecture","Graphics Processing Unit","Image processing","Computer Sciences","Plant Sciences"],"languages":["en"],"rights":["<p>Copyright is held by the author. User is responsible for all copyright compliance.</p>","James Michael Balasalle"],"rights_urls":[],"identifier_entries":[],"person_identifier_entries":[]},"links":{"outbound_url":"https://digitalcommons.du.edu/etd/756","outbound_label":"Repository record","outbound_source":"dc:identifier","record_url":"https://digitalcommons.du.edu/etd/756","record_label":"Repository record","record_kind":"record","record_source":"dc:identifier","download_url":null,"download_label":null,"download_source":null,"access_status":null,"embargo_until":null,"access_note":null},"source_record":{"url":"https://digitalcommons.du.edu/do/oai/?verb=GetRecord&metadataPrefix=oai_etdms&identifier=oai%3Adigitalcommons.du.edu%3Aetd-1755","prefix":"oai_etdms"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Matthew J. Rutherford, Ph.D.","Mario Lopez","Mohammad H. Mahoor"]},{"key":"dc:creator","label":"Author","values":["Balasalle, James Michael"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date.available","label":"Dc Date Available","values":["2001-01-01T08:00:00Z"]},{"key":"dc:date.copyright","label":"Dc Date Copyright","values":["2011-01-01T08:00:00Z"]},{"key":"dc:date.created","label":"Dc Date Created","values":["2011-01-01T08:00:00Z"]},{"key":"thesis:degree_level","label":"Degree Level","values":["Masters Thesis"]},{"key":"thesis:degree_name","label":"Degree Name","values":["M.S."]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Cellular automata","Compute Unified Device Architecture","Graphics Processing Unit","Image processing","Computer Sciences","Plant Sciences"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["en"]},{"key":"dc:rights","label":"Dc Rights","values":["<p>Copyright is held by the author. User is responsible for all copyright compliance.</p>"]},{"key":"dc:rights.holder","label":"Dc Rights Holder","values":["James Michael Balasalle"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["https://digitalcommons.du.edu/etd/756"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description.abstract","label":"Abstract","values":["Today's graphical processing units have hundreds of individual processing cores that can be used for general purpose computation of mathematical and scientific problems. Due to their hardware architecture, these devices are especially effective when solving problems that exhibit a high degree of spatial locality. Cellular automata use small, local neighborhoods to determine successive states of individual elements and therefore, provide an excellent opportunity for the application of general purpose GPU computing. However, the GPU presents a challenging environment because it lacks many of the features of traditional CPUs, such as automatic, on-chip caching of data. To fully realize the potential of a GPU, specialized memory techniques and patterns must be employed to account for their unique architecture. Several techniques are presented which not only dramatically improve performance, but, in many cases, also simplify implementation. Many of the approaches discussed relate to the organization of data in memory or patterns for accessing that data, while others detail methods of increasing the computation to memory access ratio. The ideas presented are generic, and applicable to cellular automata models as a whole. Example implementations are given for several problems, including the Game of Life and Gaussian blurring, while performance characteristics, such as instruction and memory accesses counts, are analyzed and compared. A case study is detailed, showing the effectiveness of the various techniques when applied to a larger, real-world problem. Lastly, the reasoning behind each of the improvements is explained, providing general guidelines for determining when a given technique will be most and least effective."]},{"key":"dc:description.provenance","label":"Dc Description Provenance","values":["Received from ProQuest"]},{"key":"dc:format","label":"Dc Format","values":["application/pdf"]},{"key":"dc:format.extent","label":"Dc Format Extent","values":["119 p."]},{"key":"dc:title","label":"Title","values":["Memory Access Patterns for Cellular Automata Using GPGPUs"]}]}],"canonical_facts":{"dc:contributor":["Matthew J. Rutherford, Ph.D.","Mario Lopez","Mohammad H. Mahoor"],"dc:creator":["Balasalle, James Michael"],"dc:date.available":["2001-01-01T08:00:00Z"],"dc:date.copyright":["2011-01-01T08:00:00Z"],"dc:date.created":["2011-01-01T08:00:00Z"],"dc:description.abstract":["Today's graphical processing units have hundreds of individual processing cores that can be used for general purpose computation of mathematical and scientific problems. Due to their hardware architecture, these devices are especially effective when solving problems that exhibit a high degree of spatial locality. Cellular automata use small, local neighborhoods to determine successive states of individual elements and therefore, provide an excellent opportunity for the application of general purpose GPU computing. However, the GPU presents a challenging environment because it lacks many of the features of traditional CPUs, such as automatic, on-chip caching of data. To fully realize the potential of a GPU, specialized memory techniques and patterns must be employed to account for their unique architecture. Several techniques are presented which not only dramatically improve performance, but, in many cases, also simplify implementation. Many of the approaches discussed relate to the organization of data in memory or patterns for accessing that data, while others detail methods of increasing the computation to memory access ratio. The ideas presented are generic, and applicable to cellular automata models as a whole. Example implementations are given for several problems, including the Game of Life and Gaussian blurring, while performance characteristics, such as instruction and memory accesses counts, are analyzed and compared. A case study is detailed, showing the effectiveness of the various techniques when applied to a larger, real-world problem. Lastly, the reasoning behind each of the improvements is explained, providing general guidelines for determining when a given technique will be most and least effective."],"dc:description.provenance":["Received from ProQuest"],"dc:format":["application/pdf"],"dc:format.extent":["119 p."],"dc:identifier":["https://digitalcommons.du.edu/etd/756"],"dc:language":["en"],"dc:rights":["<p>Copyright is held by the author. User is responsible for all copyright compliance.</p>"],"dc:rights.holder":["James Michael Balasalle"],"dc:subject":["Cellular automata","Compute Unified Device Architecture","Graphics Processing Unit","Image processing","Computer Sciences","Plant Sciences"],"dc:title":["Memory Access Patterns for Cellular Automata Using GPGPUs"],"thesis:degree_level":["Masters Thesis"],"thesis:degree_name":["M.S."]},"updated_at":"2026-11-19T07:54:02Z"}