We present the design and implementation of the Standard Template Adap- tive Parallel Library (stapl) pList, a parallel container that has the properties of a sequential list, but allows for scalable concurrent access when used in a paral- lel program. The stapl is a parallel programming library that extends C with support for parallelism. stapl provides a collection of distributed data structures (pContainers) and parallel algorithms (pAlgorithms) and a generic methodology for extending them to provide customized functionality. stapl pContainers are thread-safe, concurrent objects, providing appropriate interfaces (pViews) that can be used by generic pAlgorithms. The pList provides Standard Template Library (stl) equivalent methods, such as insert, erase, and splice, additional methods such as split, and efficient asyn- chronous (non-blocking) variants of some methods for improved parallel performance. List related algorithms such as list ranking, Euler Tour (ET), and its applications to compute tree based functions can be computed efficiently and expressed naturally using the pList. Lists are not usually considered useful in parallel algorithms because they do not allow random access to its elements. Instead, they access elements through a serializing traversal of the list. Our design of the pList, which consists of a collec- tion of distributed lists (base containers), provides almost random access to its base containers. The degree of parallelism supported can be tuned by setting the number of base containers. Thus, a key feature of the pList is that it offers the advantages of a classical list while enabling scalable parallelism. We evaluate the performance of the stapl pList on an IBM Power 5 cluster and on a CRAY XT4 massively parallel processing system. Although lists are generally not considered good data structures for parallel processing, we show that pList methods and pAlgorithms, and list related algorithms such as list ranking and ET technique operating on pLists provide good scalability on more than 16, 000 processors. We also show that the pList compares favorably with other dynamic data structures such as the pVector that explicitly support random access.

<p>Antalet kretskort som monteras i multikortssystem, till exempel telekommunikationssystem, ökar ständigt. Samtidigt som ytmonteringstekniken och packningstekniken blir allt bättre utvecklas även tillverkningsmetoderna för olika integrerade komponenter, vilket medför att varje kretskort rymmer allt fler integrerade komponenter. Detta gör att testning av integrerade komponenter och multikortsystem blir alltmer komplex. En förutsättning för att kunna genomföra effektiv testning är standarder. Standarder över hur testning ska genomföras medför att en komponent som uppfyller kraven från en standard är direkt utbytbar mot en komponent från en annan tillverkare som uppfyller kraven från samma standard. En god standard bidrar även till att utvecklingen drivs åt samma håll istället för att varje tillverkare har sin egen lösning och ett eget gränssnitt, vilket dessutom leder till att ett antal olika gränssnittsomvandlare behövs för att koppla samman olika komponenter. Internal Joint Test Action Group (IJTAG) arbetar just nu med att ta fram en standard för inbäddade testinstrument på mikronivå. De inbäddade instrumenten kan stödja karaktärisering av komponenter likväl som strukturell och funktionell testning. På makronivå arbetar System Joint Test Action Group (SJTAG) med att ta fram en standard för testadministration. Den främsta uppgiften är att koppla samman IJTAG-standarden med systemtestadministrationen. Behovet av ett kommunikationsprotokoll mellan dessa båda är stort. I denna rapport utvärderas Standard Test and Programming Language (STAPL) i syfte att se hur det passar som länk mellan testmanager och inbäddade instrument. Vidare identifieras ett antal brister i STAPL och ett förslag på en vidareutveckling av språket tas fram. Denna vidareutveckling syftar till att göra språket mer dynamiskt och passande för inbäddad testning via Boundary-Scan-protokollet. Slutligen implementeras en demonstrator som består av mjukvara som exekveras på en PC och en Field Programmable Gate Array (FPGA) som tjänar som testobjekt.</p>

Antalet kretskort som monteras i multikortssystem, till exempel telekommunikationssystem, ökar ständigt. Samtidigt som ytmonteringstekniken och packningstekniken blir allt bättre utvecklas även tillverkningsmetoderna för olika integrerade komponenter, vilket medför att varje kretskort rymmer allt fler integrerade komponenter. Detta gör att testning av integrerade komponenter och multikortsystem blir alltmer komplex. En förutsättning för att kunna genomföra effektiv testning är standarder. Standarder över hur testning ska genomföras medför att en komponent som uppfyller kraven från en standard är direkt utbytbar mot en komponent från en annan tillverkare som uppfyller kraven från samma standard. En god standard bidrar även till att utvecklingen drivs åt samma håll istället för att varje tillverkare har sin egen lösning och ett eget gränssnitt, vilket dessutom leder till att ett antal olika gränssnittsomvandlare behövs för att koppla samman olika komponenter. Internal Joint Test Action Group (IJTAG) arbetar just nu med att ta fram en standard för inbäddade testinstrument på mikronivå. De inbäddade instrumenten kan stödja karaktärisering av komponenter likväl som strukturell och funktionell testning. På makronivå arbetar System Joint Test Action Group (SJTAG) med att ta fram en standard för testadministration. Den främsta uppgiften är att koppla samman IJTAG-standarden med systemtestadministrationen. Behovet av ett kommunikationsprotokoll mellan dessa båda är stort. I denna rapport utvärderas Standard Test and Programming Language (STAPL) i syfte att se hur det passar som länk mellan testmanager och inbäddade instrument. Vidare identifieras ett antal brister i STAPL och ett förslag på en vidareutveckling av språket tas fram. Denna vidareutveckling syftar till att göra språket mer dynamiskt och passande för inbäddad testning via Boundary-Scan-protokollet. Slutligen implementeras en demonstrator som består av mjukvara som exekveras på en PC och en Field Programmable Gate Array (FPGA) som tjänar som testobjekt.

Multi-core architectures are present throughout a large selection of computing devices from cell phones to super-computers. Parallel applications running on these devices solve bigger problems in a shorter time. Writing those applications is a difficult task for programmers. They need to deal with low-level parallel mechanisms such as data distribution, inter-processor communication, and task placement. The goal of the Standard Template Adaptive Parallel Library (STAPL) is to provide a generic high-level framework to develop parallel applications. One of the first steps of a parallel application is to partition and distribute the data throughout the system. An important data structure for parallel applications to store large amounts of data and model many types of relations is the graph. A mesh, which is a special type of graph, is often used to model a spatial domain in scientific applications. Graph and mesh partitioning has many applications such as VLSI circuit design, parallel task scheduling, and data distribution. Data distribution, significantly impacts the performance of a parallel application. In this thesis, we introduce the STAPL Parallel Graph Partitioner Framework. This framework provides a generic infrastructure to partition arbitrary graphs and meshes and to build customized partitioners. It includes the state of the art parallel k-way multilevel scheme to partition arbitrary graphs, a parallel mesh partitioner with parameterized partition shape, and a customized partitioner used for discrete ordinates particle transport computations. This framework is also part of a generic library, STAPL, allowing the partitioning of the data and development of the whole parallel application to be done in the same environment. We show the user-friendly interface of the framework and its scalability for partitioning different mesh and graph benchmarks on a Cray XE6 system. We also highlight the performance of our customized unstructured mesh partitioner for a discrete ordinates particle transport code. The developed columnar decompositions significantly reduce the execution time of simultaneous sweeps on unstructured meshes.