GPU accelerated maximum cardinality matching algorithms for bipartite graphs

We design, implement, and evaluate GPU-based algorithms for the maximum cardinality matching problem in bipartite graphs. Such algorithms have a variety of applications in computer science, scientific computing, bioinformatics, and other areas. To the best of our knowledge, ours is the first study which focuses on GPU implementation of the maximum cardinality matching algorithms. We compare the proposed algorithms with serial and multicore implementations from the literature on a large set of real-life problems where in majority of the cases one of our GPU-accelerated algorithms is demonstrated to be faster than both the sequential and multicore implementations.

Introduction
Bipartite graph matching is one of the fundamental problems in graph theory and combinatorial optimization. The problem asks for a maximum set of vertex disjoint edges in a given bipartite graph. It has many applications in a variety of fields such as image processing [17], chemical structure analysis [15], and bioinformatics [2] (see also another two discussed by Burkard et al. [4,Section 3.8]). Our motivating application lies in solving sparse linear systems of equations, as algorithms for computing a maximum cardinality bipartite matching are run routinely in the related solvers. In this setting, bipartite matching algorithms are used to see if the associated coefficient matrix is reducible; if so, substantial savings in computational requirements can be achieved [7,Chapter 6].
Achieving good parallel performance on graph algorithms is challenging, because they are memory bounded, and there are poor localities of the mem-ory accesses. Moreover, because of the irregularity of the computations, it is difficult to exploit concurrency. Algorithms for the matching problem are no exception. There have been recent studies that aim to improve the performance of matching algorithms on multicore and manycore architectures. For example, Vasconcelos and Rosenhahn [18] propose a GPU implementation of an algorithm for the maximum weighted matching problem on bipartite graphs. Fagginger Auer and Bisseling [10] study an implementation of a greedy graph matching on GPU. Ç atalyürek et al. [5] propose different greedy graph matching algorithms for multicore architectures. Azad et al. [1] introduce several multicore implementations of maximum cardinality matching algorithms on bipartite graphs.
We propose GPU implementations of two maximum cardinality matching algorithms. We analyze their performance and employ further improvements. We thoroughly evaluate their performance with a rigorous set of experiments on many bipartite graphs from different applications. The experimental results conclude that one of the proposed GPU-based implementation is faster than its existing multicore counterparts.
The rest of this paper is organized as follows. The background material, some related work, and a summary of contributions are presented in Section 2. Section 3 describes the proposed GPU algorithms. The comparison of the proposed GPU-based implementations with the existing sequential and multicore implementations is given in Section 4. Section 5 concludes the paper.

Background and contributions
and a set of edges E such that for each edge, one of the endpoints is in V 1 and other is in V 2 . Since our motivation lies in the sparse matrix domain, we will refer to the vertices in the two classes as row and column vertices.
A matching M in a graph G is a subset of edges E where a vertex in V 1 ∪ V 2 is in at most one edge in M. Given a matching M, a vertex v is said to be matched by M if v is in an edge of M, otherwise v is called unmatched. The cardinality of a matching M, denoted by |M|, is the number of edges in M. A matching M is called maximum, if no other matching M with |M | > |M| exists. For a matching M, a path P in G is called an M-alternating if its edges are alternately in M and not in M. An M-alternating path P is called M -augmenting if the start and end vertices of P are both unmatched.
There are three main classes of algorithms for finding the maximum cardinality matchings in bipartite graphs. The first class of algorithms is based on augmenting paths (see a detailed summary by Duff et al. [8]). Pushrelabel-based algorithms form a second class [12]. A third class, pseudoflow algorithms, is based on a more recent work [13]. There are O( √ nτ ) algorithms in the first two classes (e.g., Hopcroft-Karp algorithm [14] and a variant of the push relabel algorithm [11]), where n is the number of vertices and τ is the number of edges in the given bipartite graph. This is asymptotically best bound for practical algorithms. Most of the other known algorithms in the first two classes and in the third class have the running time complexity of O(nτ ). These three classes of algorithms are described and compared in a recent study [16]. It has been demonstrated experimentally that the champions of the first two families are comparable in performance and better than that of the third family. Since we investigate GPU acceleration of augmenting-path-based algorithms, a brief description of them is given below (the reader is invited to two recent papers [8,16] and the original resources cited in those papers for other algorithms).
Algorithms based on augmenting paths follow the following common pattern. Given an initial matching M (possible empty), they search for an M-augmenting path P. If none exists, then the matching M is maximum by a theorem of Berge [3]. Otherwise, the augmenting path P is used to increase the cardinality of M by setting M = M ⊕ E(P) where E(P) is the edge set of the path P, and M ⊕ E(P) = (M ∪ E(P)) \ (M ∩ E(P)) is the symmetric difference. This inverts the membership in M for all edges of P. Since both the first and the last edge of P were unmatched in M, we have |M ⊕ E(P)| = |M| + 1. The augmenting-path-based algorithms differ in the way these augmenting paths are found and the associated augmentations are realized. They mainly use either breadth-first-search (BFS), or depth-firstsearch (DFS), or combination of these two techniques to locate and perform the augmenting paths.
Multicore counterparts of a number of augmenting-path based algorithms are proposed in a recent work [1]. The parallelization of these algorithms is achieved by using atomic operations at BFS and/or DFS steps of the algorithm. Although using atomic operations might not harm the performance on a multicore machine, they should be avoided in a GPU implementation because of very large number of concurrent thread executions.
As a reasonably efficient DFS is not feasible with GPUs, we accelerate two BFS-based algorithms, called HK [14] and HKDW [9]. HK has the best known worst-case running time complexity of O( √ nτ ) for a bipartite graph with n vertices and τ edges. HKDW is a variant of HK and incorporates techniques to improve the practical running time while having the same worst-case time complexity. Both of these algorithms use BFS to locate the shortest augmenting paths from unmatched columns, and then use DFSbased searches restricted to a certain part of the input graph to augment along a maximal set of disjoint augmenting paths. HKDW performs another set of DFS-based searches to augment using the remaining unmatched rows. As is clear, the DFS-based searches will be a big obstacle to achieve efficiency. In order to overcome this hurdle, we propose a scheme which al-ternates the edges of a number of augmenting paths with a parallel scheme that resembles to a breadth expansion in BFS. The proposed scheme offers a high degree of parallelism but does not guarantee a maximal set of augmentations, potentially increasing the worst case time complexity to O(nτ ) on a sequential machine. In other words, we trade theoretical worst case time complexity with a higher degree of parallelism to achieve better practical running time with a GPU.

Methods
We propose two algorithms for the GPU implementation of maximum cardinality matching. These algorithms use BFS to find augmenting paths, speculatively perform some of them, and fix any inconsistencies that can be resulting from speculative augmentations.
The overall structure of the first GPU-based algorithm is given in Algorithm 1, APsB. It largely follows the common structure of most of the existing sequential algorithms, and corresponds to HK. It performs a combined BFS starting from all unmatched columns to find unmatched rows, thus locating augmenting paths. Some of those augmentations are then realized using a function called Alternate (will be described later). The parallelism is exploited inside the InitBfsArray, BFS, Alternate, and if augmenting path f ound then The outer loop of Algorithm 1 iterates until no more augmenting paths are found, thereby guaranteeing a maximum matching. The inner loop is responsible from completing the breadth-first-search of the augmenting paths. A single iteration of this loop corresponds to a level of BFS. The inner loop iterates until all shortest augmenting paths are found. Then, the edges in these shortest augmenting paths are alternated inside Alternate function. Unlike the sequential HK algorithm, APsB does not find a maximal set of augmenting paths.
By removing the lines 9 and 10 of Algorithm 1, another matching algorithm is obtained. This method will continue with the BFSs until all possible unmatched rows are found; it can be therefore considered as the GPU implementation of the HKDW algorithm. This variant is called APFB.

Algorithm 2: BFS Kernel Function-1 (GPUBFS)
Data: bf s level, bf s array, cxadj, cadj, nc, rmatch, vertex inserted, augmenting path f ound 1 process cnt ← getP rocessCount(nc); 2 for i from 0 to process cnt − 1 do The GPU threads partition the columns vertices in a single dimension. Each thread with id tid is assigned a number of columns which is obtained via the following function: Once the number of columns are obtained, the threads traverse their first assigned column vertex. The indices of the columns assigned to a thread differ by tot thread num to allow coalesced global memory accesses. Threads traverse the neighboring row vertices of the current column, if its BFS level is equal to the current bf s level. If a thread encounters a matched row during the traversal, its matching column is retrieved. If the column is not traversed yet, its bf s level is marked on bf s array. On the other hand, when a thread encounters an unmatched row, an augmenting path is found. In this case, the match of the neighbor row is set to −2, and this information is used by Alternate later.

Algorithm 3: Alternate
Data: cmatch, rmatch, nc, nr, predecessor 1 process vcnt ← getP rocessCount(nr); 2 for i from 0 to process vcnt − 1 do  Algorithm 3 gives the description of the Alternate function. This kernel alternates the matching edges with unmatching edges of the augmenting paths found; some of those paths end up being augmenting ones and some are only partially alternated. Here, each thread is assigned a number of rows. Since rmatch of an unmatched row (that is also an endpoint of an augmenting path) has been set to −2 in the BFS kernel, only the threads whose row vertex's match is −2 start Alternate. Since there might be several augmenting paths for an unmatched column, race conditions while writing on cmatch and rmatch arrays are possible. Such a race condition might cause infinite loops (inner while loop) or inconsistencies, if care is not taken. We prevent these by checking the predecessor of a matched row (line-8). For example, in Fig. 1, two different augmenting paths that end with r 2 and r 3 are found for c 1 . If the thread of r 2 starts before the thread of r 3 in Alternate, the match of c 2 will be updated to r 2 (line-10). Then, r 3 's thread will read matched row of c 2 as r 2 (line-7). This would cause an infinite loop without the check at line-8. Inconsistencies may occur when the threads of r 2 and r 3 are in the same warp. In this case, the if-check will not hold for both threads, and their row vertices will be written on cmatch (line-10). Since only one thread will be successful at writing, this will cause an inconsistency. Such inconsistencies are fixed by This array holds the root (as the index of the column vertex) of an augmenting path, and this information is transferred down during BFS. Whenever an augmenting path is found, the entry in bf s array for the root of the augmenting path is set to L 0 − 2. This information is used at the beginning of BFS kernel. No more BFS traversals is done, if an augmenting path is found for the root of the traversed column vertex. Therefore, while the method increases the global memory accesses by introducing an extra array, it provides an early exit mechanism for BFS.
We further improve GPUBFS-WR by making use of the arrays root and bf s array. BFS kernels might find several rows to match with the same unmatched column, and set rmatch[·] to −2 for each. These cause Alternate to start from several rows that can be matched with the same unmatched column. Therefore, it may perform unnecessary alternations, until these augmenting paths intersect. Conflicts may occur at these intersection points (which are then resolved with FixMatching function). By choosing L 0 as 2, we can limit the range of the values that bf s array takes to positive numbers. Therefore, by setting the bf s array to −(neighbor row) at line 19 of Algorithm 4, we can provide more information to the Alternate function. With this, Alternate can determine the beginning and the end of an augmenting path, and it can alternate only among the correct augmenting paths. APsB-GPUBFS-WR (and Alternate function used together) includes these improvements. However, they are not included in APFB-GPUBFS-WR since they do not improve its performance.

Experiments
The running time of the proposed implementations are compared against the sequential HK and PFP implementations [8], and against the multicore  is used to initialize all tested algorithms. We compare the running time of the matching algorithms after this common initialization. Two different main algorithms APFB and APsB can use two different BFS kernel functions (GPUBFS and GPUBFS-WR). Moreover, each of these algorithms can have two versions (i) CT: uses a constant number of threads with fixed number of grid and block size (256 × 256) and assigns multiple vertices to each thread; (ii) MT: tries to assign one vertex to each thread. The number of threads used in the second version is chosen as MT = min(nc, #threads) where nc is the number of columns, and #threads is the maximum number of threads of the architecture. Therefore, we have eight GPU-based algorithms.
The algorithms are run on bipartite graphs corresponding to 70 different matrices from variety of classes at UFL matrix collection [6]. We also permuted the matrices randomly by rows and columns and included them as a second set (labeled RCP). These permutations usually render the problems harder for the augmenting-path-based algorithms [8]. For both sets, we report the performance for a smaller subset which contains those matrices in which at least one of the sequential algorithms took more than one second. We call these sets O S1 (28 matrices) and RCP S1 (50 matrices). We also have another two subsets called O Hardest20 and RCP Hardest20 that contain the set of 20 matrices on which the sequential algorithms required the longest running time.
First, we compare the performance of the proposed GPU algorithms.   Table 1 shows the geometric mean of the running time on different sets. As we see from the table, using constant number of threads (CT) always increases the performance of an algorithm, since it increases the granularity of the work performed by each thread. GPUBFS-WR is always faster than GPUBFS. This is because of the unnecessary BFS traversals in the GPUBFS algorithm. GPUBFS cannot determine whether an augmenting path has already been found for an unmatched column, therefore it will continue to explore. This unnecessary BFS traversals not only increase the BFS time, but also reduce the likelihood of finding an augmenting path for other unmatched columns. Moreover, the Alternate scheme turns out to be more suitable for APFB than APsB, in which case it can augment along more paths (there is a larger set of possibilities). For example, Figs. 2(a) and 2(b) show the number of BFS iterations and the number of BFS levels in each iteration for, respectively, Hamrle3 and Delanuay n23 graphs. As clearly seen from both of the figures, APFB variants converges in smaller number of iterations than APsB variants; and for most of the graphs, the total number of BFS kernel calls are less for APFB (as in Fig. 2(a)). However, for a small subset of the graphs, although the augmenting path exploration of APsB converges in larger number of iterations, the numbers of the BFS levels in each iterations are much less than APFB (as in Fig. 2(b)). Unlike the general case, APsB outperforms APFB in such cases. Since APFB using GPUBFS-WR and CT almost always obtains the best performance, we only compare the performance of this algorithm with other implementations in the following. Figures 3(a) and 3(b) give the log-scaled speedup profiles of the best GPU and multicore algorithms on the original and permuted graphs. The speedups are calculated with respect to the fastest of the sequential algorithms PFP and HK (on the original graphs HK was faster; on the permuted ones PFP was faster). A point (x, y) in the plots corresponds to the probability of obtaining at least 2 x speedup is y. As the plots show, the GPU algorithm has the best overall speedup. It is faster than the sequential HK  algorithm for 86% of the original graphs, while it is faster than PFP on 76% of the permuted graphs. P-DBFS obtains the best performance among the multicore algorithms. However, its performance degrades on permuted graphs. Although P-PFP is more robust than P-DBFS to permutations, its overall performance is inferior to that of P-DBFS. P-HK is outperformed by the other algorithms in both sets.  show the performance profiles of the GPU and multicore algorithms. A point (x, y) in this plot means that with y probability, the algorithm obtains a performance that is at most x times worse than the best running time. The plots clearly show the separation among the GPU algorithm and the multicore ones, especially for original graphs and for x ≤ 7 for the permuted ones, thus marking GPU as the fastest in most cases. In particular, GPU algorithm obtains the best performance in 61% of the original graphs, while this ratio increases to 74% for the permuted ones. Figure 5 gives the overall speedups. The proposed GPU algorithm obtains average speedup values of at least 3.61 and 3.54 on, respectively, original and permuted graphs. The speedups increase for the hardest instances, where the GPU algorithm achieves 3.96 and 9.29 speedup, respectively, on original and permuted graphs.  on the complete set of graphs can be found at http://bmi.osu.edu/hpc/ software/matchmaker2/maxCardMatch.html). As seen from this table, except six instances among the original graphs and another two among the permuted graphs, the GPU algorithm is faster than the best sequential algorithm. It is also faster than the multicore ones in all, except five original graphs.

Concluding remarks
We proposed a parallel BFS based GPU implementation of maximum cardinality matching algorithm for bipartite graphs. We presented experiments on various datasets, and compared the performance of the proposed GPU implementation against sequential and multicore algorithms. The experiments showed that the proposed GPU implementations are faster than the existing parallel multicore implementations. The speedups achieved with respect to well-known sequential implementations varied from 0.03 to 629.19, averaging 9.29 on a set of 20 hardest problems with respect to the fastest sequential algorithm. A GPU is a restricted memory device. Although, an out-of-core or distributed-memory type algorithm is amenable when the graph does not fit into the device, a direct implementation of these algorithms will surely not be efficient. We plan to investigate the techniques to obtain good matching performance for extreme-scale bipartite graphs on GPUs.


extfieldsofstudy:
Computer Science
Biology

text:
Dimension Reduction of Large AND-NOT Network Models

Boolean networks have been used successfully in modeling biological networks and provide a good framework for theoretical analysis. However, the analysis of large networks is not trivial. In order to simplify the analysis of such networks, several model reduction algorithms have been proposed; however, it is not clear if such algorithms scale well with respect to the number of nodes. The goal of this paper is to propose and implement an algorithm for the reduction of AND-NOT network models for the purpose of steady state computation. Our method of network reduction is the use of"steady state approximations"that do not change the number of steady states. Our algorithm is designed to work at the wiring diagram level without the need to evaluate or simplify Boolean functions. Also, our implementation of the algorithm takes advantage of the sparsity typical of discrete models of biological systems. The main features of our algorithm are that it works at the wiring diagram level, it runs in polynomial time, and it preserves the number of steady states. We used our results to study AND-NOT network models of gene networks and showed that our algorithm greatly simplifies steady state analysis. Furthermore, our algorithm can handle sparse AND-NOT networks with up to 1000000 nodes.

Introduction
Boolean networks (BN) have been used successfully in modeling biological networks, such as gene regulatory networks [1][2][3][4][5] and provide a good framework for theoretical analysis [6,7]. However, the analysis of large networks is not trivial. For example, even the problem of finding or counting steady states has been shown to be hard [8][9][10]. Even comprehensive sampling of the phase space is of limited use, once a model contains 50 or 100 nodes.
In order to simplify the analysis of such networks, several model reduction algorithms have been proposed [11][12][13]. However, it is not clear if such algorithms scale well with respect to the number of nodes. These reduction algorithms are based on using "steady state approximations" to remove nodes in a BN. More precisely, to remove a node i in a Boolean network, f = (f 1 , . . . , f m ) : {0, 1} n → {0, 1} n , one assumes that the i-th variable is in steady state and replaces all instances of the i-th variable by its Boolean function. For example, we can reduce the BN f (x 1 , x 2 , x 3 ) = (¬x 3 , x 1 ∨ ¬x 3 , x 1 ∧ ¬x 2 ), by making the substitution x 3 → f 3 = x 1 ∧ ¬x 2 ; then, we obtain the reduced BN h(x 1 , x 2 ) = (¬(x 1 ∧ ¬x 2 ), x 1 ∨ ¬(x 1 ∧ ¬x 2 )). This process can be repeated iteratively without changing the number of steady states.
There are two important aspects in the reduction of BNs. One is the representation of the Boolean functions (e.g. Boolean operators, polynomials, binary decision diagrams, truth tables), and the other is the way in which the reduced network is simplified to ensure that the wiring diagram is consistent with the Boolean functions (e.g. Boolean algebra, polynomial algebra, substitution). It is in these two aspects where algorithms can stop being scalable. For example, although polynomial algebra makes the manipulation of Boolean functions very systematic, the polynomial representation of simple Boolean functions can be large. For instance, storing x 1 ∨ x 2 ∨ . . . ∨ x k and ¬x 1 ∧ ¬x 2 ∧ . . . ∧ ¬x k in polynomial form grows exponentially with respect to k. On the other hand, although using Boolean operators can be more intuitive and efficient at representing Boolean functions, their simplification also grows exponentially with respect to the number of variables.
The reduction algorithm in this paper is tailored specifically to the computation of steady states of AND-NOT networks and takes advantage of the sparsity typical of gene regulatory networks. AND-NOT networks are BNs where the functions are of the form y i1 ∧ y i2 ∧ · · · ∧ y ir where y ij ∈ {x ij , ¬x ij }. We focus on AND-NOT networks because they have been shown to be "general enough" for modeling and "simple enough" for theoretical analysis [14][15][16]. Also, synthetic AND-NOT gene networks can be designed by coupling synthetic AND gates (e.g. [17]) and negative regulation. Also, AND-NOT functions are a particular case of nested canalizing functions, which have been proposed as a class of BNs for modeling biological systems [18][19][20][21][22].
Our dimension reduction algorithm for AND-NOT networks has two important properties: First, it preserves all steady state information; more precisely, there is a one-to-one correspondence between the steady states of the original and reduced network. Second, it runs in polynomial time.
As in previous reduction methods, the main idea of our algorithm is that one can use steady state approximations without changing the number of steady states; however, there are some key differences. First, the only reduction steps that are allowed are those that result in a reduced AND-NOT network. Second, since we are using AND-NOT networks only, we can make additional reductions that cannot be done with other networks. It is important to mention that AND-NOT networks are completely determined by their wiring diagrams. This is important for two reasons: First, we can store AND-NOT networks efficiently using their wiring diagrams and thus avoid the problem that the polynomial representation has. Second, we can state all reduction steps and simplification of the reduced network at the wiring diagram level and thus avoid the problem that the Boolean representation has.  given by: is an AND-NOT network. For example, f 1 = j∈{2,4} x j ∧ j∈{5} ¬x j .
For example, it is easy to check that 000011 is a steady state of the AND-NOT network in Example 2.2.
Definition 2.4. The extended wiring diagram of an AND-NOT network is defined as a signed directed graph G = (V G , E G ) with vertices V G = {0, 1, . . . , n} (or {0, x 1 , . . . , x n }) and edges E G given as follows: (i, j, +) ∈ E G ((i, j, −) ∈ E G , respectively) if x i is a positive (negative, respectively) regulator of f j . If f j = 0, then (0, j, +) ∈ E G . Positive edges are denoted by -◮ and negative edges by -•. We will refer to the extend wiring diagram as simply wiring diagram.
For example, the wiring diagram of the AND-NOT network in Example 2.2 is shown in Figure 1.

Reduction of AND-NOT Networks
3.1. Reduction Steps and Algorithm. As mentioned in the Introduction, the idea is to assume that nodes are in steady state and remove them from the network by replacing the variable by the corresponding AND-NOT function. At the wiring diagram level, the idea is to remove nodes and insert edges so that the sign of the edges are "consistent". For example, a path i-◮ j-• k should become i-• k after removing node j; and i-• j-• k should become i-◮ k after removing node j. The actual rules for doing this depend on the the properties of the node being removed and the incoming and outgoing edges. Figure 2 shows the steps at the wiring diagram level. We claim that each of these reduction steps do not change the number of steady states and that the one-to-one correspondence is algorithmic. The proofs follow directly from basic properties of Boolean algebra, so we only give the idea behind each reduction step. • Reduction Step R0. Here node i does not have any outgoing edges, so this node does not contribute to the number of steady states and can be removed. Note that given a steady state of the reduced AND-NOT network, the steady state of the original network can be found simply by inserting (in the i-th entry) x i = f i . Note that this reduction step is also valid for general BNs. • Reduction Step R1. Here we have f i = 0; and we remove node i by replacing x i with f i = 0. For example, if i-◮ j, then f j = x i ∧ w j for some AND-NOT function w j . By replacing x i with 0 we obtain f j = 0 ∧ w j = 0; that is, we add the edge 0-◮ j and remove all other incoming edges of j. On the other hand, if i-• k, then f k = ¬x i ∧ w k for some AND-NOT function w k . By replacing x i with 0 we obtain f j = ¬0 ∧ w k = w k ; that is, the edge i-• k is removed and all other edges towards k remain present. Note that given a steady state of the reduced AND-NOT network, the steady state of the original network can be found simply by inserting (in the i-th entry) x i = 0. We also notice that this reduction step is also valid for general BNs, but not at the wiring diagram level (the wiring diagram of the reduced network depends on the actual Boolean functions). • Reduction Step R2. Here we have f i = 1; and we remove node i by replacing By replacing x i with 1 we obtain f j = 1 ∧ w j = w j ; that is, the edge i-• j is removed and all other edges towards j remain present. On the other hand, if i-• k, then f k = ¬x i ∧ w k for some AND-NOT function w k . By replacing x i with 1 we obtain f j = ¬1 ∧ w k = 0; that is, we add the edge 0-◮ k and remove all other incoming edges of k. Note that given a steady state of the reduced AND-NOT network, the steady state of the original network can be found simply by inserting x i = 1. We also notice that this reduction step is also valid for general BNs, but not at the wiring diagram level. • Reduction Step R3, R4. For R3 we have f i = x j ∧ x k ∧ w i for some AND-NOT function w i , and a node j with Boolean function f j = ¬x k ∧ w j for some AND-NOT function w j . If we are at a steady state, then we have two cases, either In either case x i = 0, so by assuming that f i = 0 we are not changing the steady states of the AND-NOT network. That is, we add the edge 0-◮ i and remove all other incoming edges of i. The reduction step R4 is analogous. It is important to mention that this reduction step is not valid for general BNs. • Reduction Step R5. Here we have that f i = ¬x j ∧ ¬x k and f j = x k ∧ w j for some AND-NOT function w j . If we are at a steady state then we have two cases, either In either case we have x i = ¬x k , so by assuming that f i = ¬x k we are not changing the steady states. It is important to mention that this reduction step is not valid for general BNs. • Reduction Step R6, R7. For R6 we have that f i = ¬x k ; and we remove node i by replacing for some AND-NOT function w j2 , then we obtain f j2 = ¬x k ∧ w j2 , which is an AND-NOT function as well. Note that given a steady state of the reduced AND-NOT network, the steady state of the original network can be found simply by inserting x i = ¬x k . The reduction step R7 is analogous. We notice that this reduction step is also valid for general BNs, but not at the wiring diagram level. Also, the reduction is no longer valid if i has more incoming edges (the reduced network would not be an AND-NOT network). • Reduction Step R8. Here we have that all outgoing edges of i are positive. and we remove node i by replacing then we obtain f j = ¬x k1 ∧ x k2 ∧ w j , which is an AND-NOT function. Note that given a steady state of the reduced AND-NOT network, the steady state of the original network can be found simply by inserting x i = ¬x k1 ∧ x k2 . We also notice that this reduction step is also valid for general BNs, but not at the wiring diagram level. It is important to mention that the reduction is no longer valid if i has any negative outgoing edge. • Reduction Step R9. Here we have a circuit with positive edges only. If we are at a steady state, we have two cases, either x i1 = 0 or x i1 = 1. If x i1 = 0, then it follows that x i2 = 0 and working forward we obtain that x i1 = x i2 = . . . = 0. Similarly, if x i1 = 1, we obtain that x i1 = x i2 = . . . = 1. Thus, by collapsing this circuit into a single node we do not change the number of steady states. Note that given a steady state of the reduced AND-NOT network, the steady state of the original network can be found simply by inserting (x i2 , x i3 , x i4 , . . .) = (x i1 , x i1 , x i1 , . . .). Note that this reduction step is no longer valid if one of the edges in the circuit is negative. This reduction step is also valid for general BNs (removing one node at at time), but not at the wiring diagram level.
It is important to mention that reduction steps R0 − R8 cover the possible reductions where we only need to look at incoming and outgoing edges of a node i. Other reduction steps could be considered by looking upstream and downstream of a node; for example, one can generalize R3 and R4 to include longer feedforward loops (e.g.
However, their detection becomes computationally expensive. Reduction step R9 is included because such circuits can be detected in linear time [23].
The actual algorithm is given below. The idea is to iteratively apply the reduction steps until the network is no longer reducible (every time a reduction step is used, new reducible nodes can appear). Note that there are many orders in which one can apply the reduction steps, and in some cases they can result in different reduced networks (with the same number of states). Based on the performance of preliminary simulations, the order given below was chosen.
Algorithm. Input: AND-NOT network G. Output: List of steady states.
(3) Use R1, R2 to remove from G the nodes in Z. (4) Go to (1). (5) Use R3, R4 to find new nodes with input 0. (6) If nodes were found in previous step, then go to (1). (7) Use R5 to remove edges. (8) If there are nodes with a single incoming edge only, then use R6, R7 to remove them and go to (1). (9) Find nodes with positive outgoing edges only. (10) If nodes were found in previous step, then use R8 to remove them and go to (1). (11) Find circuits of length greater than 1 with positive edges only. Only use this step once. (12) If circuits were found in previous step, then reduce them using R9 and go to (1). (13) Compute the steady states of the reduced AND-NOT network. (14) Use the bijections given by the reduction steps to find the steady states of the original system. The algorithm has 3 main parts. In (1)-(12) we reduce the AND-NOT network; in (13) we compute the steady states of the reduced AND-NOT network; and in (14) we use these steady states to find the steady states of the initial AND-NOT network. Note that step R9 is used only once in the algorithm because none of the other steps create extra circuits.

Implementation and Computational Complexity.
We preliminarily implemented our algorithm in C++ and used the Boost Graph Library to manipulate graphs (code available upon request). We stored the one-to-one correspondence as an acyclic graph so that once the steady states of the reduced network are computed, one simply uses backward substitution to recover the steady states of the original network. The steady states of the reduced AND-NOT network are computed by exhaustive search.
Example 3.1. Consider the AND-NOT network given by: The wiring diagrams of this AND-NOT network, the reduced AND-NOT network, and the acyclic graph are in Figure 3 (see the Appendix for details about the format we use in our implementation). The reduced network is h(x 4 ) = x 4 , from which we easily obtain the steady states x 4 = 0, 1. The acyclic graph encodes the following substitution: For x 4 = 0 we obtain x 3 = 0, x 6 = 1, Since it is not known the average number of times each pattern in Figure 2 appears in a random AND-NOT network, it is difficult to predict the exact computational complexity of our algorithm. However, we present a heuristic estimation as follows. Let n be the number of nodes and e the number of edges; we denote with T the computational complexity. We first focus on steps (1)-(12) of the algorithm. In the worst case scenario steps (11) and (12) will have to be done at the beginning, this contributes O(n + e) to T [23]. Each detection of an individual pattern and reduction step from (1) to (10) takes constant time for each node; then, each one of these steps of the algorithm (not counting the "go to" statements) contributes O(n) to T ; and, since we have to repeat this at most n times (counting the "go to" statements), we obtain that steps (1)-(10) contribute O(n 2 ) to T . Thus, steps (1)- (12) contribute O(n + e + n 2 ) = O(n 2 ) to T . Assuming that one can check in constant time if a state in the reduced network is a steady state, step (13) contributes O(2 m ) where m is the size of the reduced AND-NOT network.
Note that the reduction part and backward substitution part contribute O(n 2 ) to T ; that is, they run in polynomial time.
Although T = O(n 2 + 2 m ) is of little improvement if m ≈ n, Boolean models of biological systems are not arbitrary and have especial properties. For example, they are sparse and have motifs such as feedforward loops (which we considered in R3−R5); also, they have few steady states when compared to random networks. Hence, one can argue that for Boolean models of biological systems, the reduced network are likely to be very small. Indeed, for the three Boolean models that we consider in the next section, the size of the reduced networks, m, did not exceed ln(n). The fact that m did not exceed ln(n) is important, because for family of networks where m = O(ln(n)), we obtain that T = O(n 2 + n k ) for some k > 0. Thus, one can conjecture that under some conditions our algorithm (including steady state computation) runs in polynomial time, but a formal statement and proof of this conjecture is outside the scope of this manuscript. However, our statistical analysis in Section 4.4 supports this.

Applications
In this section we apply our reduction algorithm to three published networks and random networks, and demonstrate that it can result in a significant reduction of the network's dimension. We denote two negative (positive) edges between i and j by a bidirectional negative (positive) edge, •-• (◭-◮); if the edges have different signs we denote them by •-◮.

Th-lymphocyte Differentiation.
Here we consider an AND-NOT model for Th-cell differentiation [4,14], The wiring diagram is shown in Figure 4 (left). The state space of this model has 2 26 ≈ 6.7 × 10 7 states.
By using our algorithm we reduce this AND-NOT network to the AND-NOT network shown in Figure 4 (right), h : {0, 1} 2 → {0, 1} 2 , given by h(x 1 , x 22 ) = (x 1 ∧¬x 22 , ¬x 1 ∧x 22 ). Notice that its state space has only 4 states, which is about 7 orders of magnitude smaller than the original state space. Since this is a small network, it is easy to find its steady states: 00, 01, and 10. Therefore, our results guarantee that the original AND-NOT model has 3 steady states which can be recovered from the steady states of the reduced network. The timing of our implementation was .00273562s (average of 1000000 repetitions).

ERBB2 Activation.
Here we consider an AND-NOT network model of ERBB2 activation based on the Boolean model in [24] (left). The wiring diagram of the equivalent AND-NOT model is shown in Figure 5. The state space of this model has 2 24 ≈ 1.6 × 10 7 states.  15 , f 24 = x 13 ∧ x 14 ∧ x 15 By using our algorithm we reduce this AND-NOT network to the AND-NOT network shown in Figure 5 (right), h : {0, 1} 1 → {0, 1} 1 given by h(x 20 ) = 1. Notice that its state space has only 2 states, which is about 7 orders of magnitude smaller than the original state space. It is easy to see that this network has a unique steady state (x 20 = 1). Therefore, the original AND-NOT model also has a unique steady state, which can be recovered from the steady state of the reduced network. The timing of the reduction is .00266462s (average of 1000000 repetitions).

T-cell receptor.
Here we consider an AND-NOT network model of the T-cell receptor based on the Boolean model in [25] (left). The wiring diagram is shown in Figure 6. The state space of this model has 2 43 ≈ 8.8 × 10 12 states. exhaustive search, one can use additional tools such as polynomial algebra [29], but as mentioned before, this was not necessary for our simulations. Table 1. Timimg, t, for the reduction algorithm (in seconds). The mean and standard deviation of t are denoted by µ t and σ t , respectively. Last row: best fit polynomial t = cn k .  We can see in Figure 7 that our reduction algorithm scales well with the number of nodes. Furthermore, our algorithm can reduce networks with 1000000 nodes. We also see that for very sparse networks (i.e. large values of γ) our algorithm scales very well. As sparsity is lost (i.e. as γ decreases), our algorithm becomes less and less scalable; however, as mentioned before, the value of γ for biochemical networks is usually between 2 and 3 for which our algorithm performs well. Also, the timings look polynomial (linear on the log-log scale), especially for large γ and n. The best fit polynomial of the form t = cn k for γ = 2 was given by c ≈ 10 −8 and k ≈ 2.025; and for γ = 3 was given by c ≈ 2 × 10 −6 and k ≈ 1.197. Note: Although using the timings at n = 10 2 for the estimation of c and k would give a smaller value of k, we did not use them because the linear relationship between log(t) and log(n) seemed to start at n = 10 3 .

Discussion
Since the problem of analyzing BNs is hard for large networks, many reduction algorithms have been proposed [11][12][13]. However, it is not clear if such algorithms scale well with the size of the network. In order to optimize reduction algorithms, it is necessary to focus on specific families of BNs.
The family of AND-NOT networks has been proposed as a special family simple enough for theoretical analysis, but general enough for modeling [14][15][16]. Thus, we propose an algorithm for network reduction for the family of AND-NOT networks. A key property of our algorithm is that it preserves steady states, so it can be very useful in steady state analysis. We applied our algorithm to three AND-NOT network models, namely, Th-cell differentiation, ERBB2 activation, and T-cell receptor. Our reduction algorithm performed very well with these models; the state space of the reduced networks were several orders of magnitude smaller than the original state space. This greatly simplified steady state computation. Using random AND-NOT networks, we showed that our algorithm scales well with the number of nodes and can handle large sparse AND-NOT networks with up to 1000000 nodes. To the best of our knowledge, no other algorithm can handle AND-NOT networks or any other class of (nonlinear) BNs of this size.
It is important to mention that since our reduction algorithm is defined using the wiring diagram only, it has the special property that it runs in polynomial time. That is, we have developed a polynomial-time algorithm that reduces the problem of finding steady states of an AND-NOT network, f : {0, 1} n → {0, 1} n , into the problem of finding the steady states of a smaller AND-NOT network, g : {0, 1} m → {0, 1} m , where m ≤ n. Also, the steady states of the reduced AND-NOT network can be used to compute the steady states of the original AND-NOT network in polynomial time. Thus, our algorithm transforms an NP-complete problem of input size n into an NP-complete problem of input size m, where m ≤ n. While this represents no theoretical improvement in the complexity of the problem, it does represent a significant improvement in the practical ability to analyze actual models that arise in molecular systems biology because they are very sparse, and in that case we typically have m << n. Also, this could provide a novel way to solve NP-complete problems by first using our polynomial-time algorithm as a pre-processing step.


An Evaluation for Model Testability approaches

Design for testability is a very important issue in software engineering. It becomes crucial in the case of Model Based Testing where models are generally not tested before using as input of Model Based Testing. The quality of design models (e.g.; UML models), has received less attention, which are main artifacts of any software design. Testability tends to make the validation phase more efficient in exposing faults during testing, and consequently to increase quality of the endproduct to meet required specifications. Testability modeling has been researched for many years. Unfortunately, the modeling of a design for testability is often performed after the design is complete. This limits the functional use of the testability model to determining what level of test coverage is available in the design. This information may be useful to help assess whether a product meets the target requirement to achieve a desired level of test coverage, but has little proactive effect on making the design more testable. Council for Innovative Research Peer Review Research Publishing System Journal: INTERNATIONAL JOURNAL OF COMPUTERS & TECHNOLOGY Vol 9, No 1 editor@cirworld.com www.cirworld.com, member.cirworld.com

Introduction
Software testing is a significant part of both the software lifecycle and quality assurance activities. In simple form, testing is the software products dynamic execution in order to show the errors presence. Software testing is costly, and it is considered as the final barrier to the software product release. Model-based testing (MBT) is an automation of black box testing technique; its major difference from the conventional methods of black box testing is that the test cases are automatically produced by software tools that develop the expected behavioral models of the software under the test (SUT). MBT has conveyed a lot of benefits. These contain errors early detection, which is measured to be very cheap. The major MBT liability is to knowing how to model SUT (Reza, Ogaard, & Malge, 2008).
Model-based testing (MBT) is a rising trend in test automation. In MBT, the SUT is modeled at an appropriate level of abstraction for testing, and tools are used to automatically create test cases based on this model. Given a set of appropriate methods and tools, MBT has been demonstrated to be a helpful and efficient means for high-level testing in diverse domains. Some benefits comprise decreased costs of maintenance in concentrating on a single high-level model, and boosted test coverage over the features expressed in the test model by the means of automated test generation (Puolitaival & Kanstrén, 2010).
Model-based testing (MBT) defendants the systematic use of software models in particular for testing activities, e.g. creation of test oracles, test execution environments and test cases. If a software model is well appropriate for activities of testing, we speak of a testable model. Thus, software models testability is a significant quality representing the degree to which a software model helps activities of testing in a given test context. The software models testability should already be analyzed and enhanced at modeling time before MBT activities start. This assists to save costs for the detection and correction of defects of testability in later stages.
For models used in model-based testing, their testability evaluation is a significant problem. Existing approaches lack some related features for a systematic and complete evaluation. Either they do (1) not think about the context of models of software, (2) not propose a systematic process for choosing and developing right dimensions, (3) not describe a reliable and general understanding of quality, or (4) not separate between subjective and objective measurements (Voigt & Engels, 2008).
Testability is a property of program that is introduced with the purpose of forecasting efforts need for testing the program. To quantify the program testability is to relate the program with some numbers to present the degree of how easy are those definite testable properties in the program to be tested. High testability software means that errors could be discovered more easily during testing (if the software exist errors). Otherwise, it is complicated to be tested and is likely to be fewer reliable. Therefore the number of tests need in a program may be taken as the quantify of its testability. There has not been an instinctively acceptable measure of program testability. Software testability is the degree to which a software artifact (i.e. a software module, software system, design document or requirements) supports testing in a test context that given. Testability is not an inherent property of a software artifact and cannot be calculated directly (such as software size). Instead testability is an extrinsic property that results from software interdependency to be tested and the test goals, test methods used, and test resources (i.e., the test context). A minor degree of testability results in enhanced test effort. In tremendous cases a testability lack may hinder software testing parts or software requirements at all (Yeh & Lin, 1998).

An Empirical Analysis of a Testability Model for Object-Oriented Programs
Authors presented a metric based testability model for object-oriented programs. The paper investigated empirically the relationship between the model and testability of classes at the code level. Testability has been investigated from the perspective of unit testing. They designed an empirical study using data collected from two open sources Java software systems for which JUnit test cases exist. To capture testability of classes, they used various metrics to quantify different characteristics of the corresponding JUnit test cases. In order to evaluate the capability of the model to predict testability of classes, they used statistical tests using correlation. The achieved results support the idea that there is a statistically significant relationship between the model and the used test case metrics (Kout et al., 2011).

Analysis of Object Oriented Complexity and Testability Using Object Oriented Design Metrics
The approach proposed in this paper revolves around the complexity and testability of object oriented design. Predicting complexity of design at class level helps to simplify the design as much as possible. Object oriented design metrics extended by the approach proposed in this paper helps to obtain the quantifiable results so that complexity of design can be predicted accurately. The approach is based on literature survey and the concepts developed are validated by mapping the metrics J u l y 1 5 , 2 0 1 3 model to the actual software projects. Literature survey concepts and estimated results obtained by actual projects verify each other. Improvements can be made to the proposed metrics. As more detailed designs are produced during later design phases, the proposed metrics can be applied to different other types of diagrams produced as a part of detailed design either in its existing form or by modifying it according to requirements. Complexity analysis at coding stage can be performed by the object oriented design metrics proposed in this paper (Khalid et al., 2010).

Metric Based Testability Model for Object Oriented Design (MTMOOD)
The proposed model for the assessment of testability in object-oriented design has been validated using structural and functional information from object oriented software. The models" ability to estimate overall testability from design information has also been demonstrated using several functionally equivalent projects where the overall testability estimate computed by model had statistically significant correlation with the assessment of overall project characteristics determined by independent evaluators. The proposed model is more practical in nature having quantitative data on testability is of immediate use in the software development process. The software developer can use such data to plan and monitor testing activities. The tester can use testability information to determine on what module to focus during testing. And finally, the software developer can use testability metrics to review code, trying to find refactoring that would improve the testability of the code (Khan & Mustafa, 2009).

Automating regression test selection based on UML designs
The authors propose a methodology supported by a prototype tool to tackle the regression test selection problem at the architecture/ design level in the context of UML-based development. Their main motivation is to enable, in the context of UMLbased development, regression test selection based on design change information, early in the change process. They also present three case studies that were used as an initial feasibility and benefit assessment. These case studies are varied in the sense that they cover very different systems and changes, in both industrial and academic settings. Results show that design changes can have a complex impact on regression test selection and that, in many cases, automation is likely to help avoid human errors. Their objective has been to ensure that regression testing was safe while minimizing regression testing effort. But they have shown that certain changes may not be visible in the design and may require additional attention during coding or a special way to document them during design. Another limitation is that, based on UML design information, test selection may not be as precise as if it was based on detailed code analysis. Improving precision by analyzing in more detail guard conditions and OCL contracts is the focus of their current research. However, their case studies have only shown one case of imprecision in classifying a test case as retestable. Despite the above limitations, by providing a methodology and t ool to perform impact analysis and regression test selection based on UML designs, the achievements are: -Higher efficiency in test selection based on the automation of design change analysis and traceability between UML designs and regression test cases.
-Better support for assessing and planning regression test effort earlier in the change process that is once design changes have been determined (Briand et al., 2009).

Automatic generation of test specifications for coverage of system state transitions
The authors have presented a novel strategy for automatic state-based system testing for achieving transition path coverage. A severe handicap in system test generation for transition coverage arises due to the fact that system state models are not developed during any pragmatic development process. This may be attributed to the fact that the state models for practical problems tend to be extremely large and complex. To overcome this problem, they synthesize a system state model of an object-oriented system from the relevant UML models. The synthesized state model is then used to generate test specifications for transition coverage. Their approach to system testing does not replace traditional testing approaches such as, method coverage, message path coverage, etc. On the other hand, their approach to testing based on transition path coverage is intended to be used in a complementary manner with traditional test techniques. The test specification generated by our approach could detect bugs not detected using traditional testing, since the fault models for the two are different (Sarma & Mall, 2009).

Improving the Testability of Object Oriented Software through Software Contracts
The main goal of the study was to establish the relationship between software testability and software contracts. The software contracts reduce the testing effort and hence improve the testability of an object oriented class. The same is demonstrated through an example of a queue class written in C++. The results show that software contracts reduce the number of test cases J u l y 1 5 , 2 0 1 3 by 50% to test a class. Hence, the software practitioners can make use of software contracts to reduce the testing effort and hence improve the testability of the software (Singh & Saha, 2010).

Construction of a Systemic Quality Model for Evaluating a Software Product
In referring to the well-known expression "build quality into software," Dromey points out that high-level quality attributes, such as reliability and maintainability, cannot be built into the software. What can be done though is to identify a set of properties (such as modules without side effects) and build them up consistently, harmoniously and fully to provide reliability and maintainability. Links must be forged between the tangible properties of the product and the high-level quality attributes. Dromey proposes three models, depending on the products resulting from each stage of the development process: requirements model, design model, and implementation quality model (programming). In comparing this model to ISO 9126, additional characteristics like process maturity and reusability are noticeable. It is important to point out the weighting Dromey gives to process maturity, an aspect not considered in previous models. This model seeks to increase understanding of the relationship between the attributes (characteristics) and the subattributes (subcharacteristics) of quality. It also attempts to pinpoint the properties of the software product that affect the attributes of quality. After analyzing various product quality models, the different quality attributes or characteristics found in each of them must be compared. Table 2.9 shows that the quality characteristics found in the majority of the models are: efficiency, reliability, maintainability, portability, usability and functionality, which have been present in more recent models. Because they are present in all the models studied, they can be considered essential and worthy of study (Ortega & Rojas, 2003).

An empirical study into class testability
Testability The ISO defines testability as""attributes of software that bear on the effort needed to validate the software product"". Binder offers an analysis of the various factors that contribute to a system"s testability, which he visualizes using the fish bone diagram as shown in below Figure. The major factors determining test effort Binder distinguishes include the testing criterion that is required, the usefulness of the documentation, the quality of the implementation, the reusability and structure of the test suite, the suitability of the test tools used, and the process capabilities. Of these factors, our study is concerned with the structure of the implementation, and on source code factors in particular. We distinguish between two categories of source code factors: factors that influence the number of test cases required testing the system, and factors that influence the effort required to develop each individual test case. We will refer to the former category as test case generation factors and to the latter category as test case construction factors, which both are discussed below (Bruntink & Van Deursen, 2006).

Contract-Based Software Component Testing with UML Models
This research takes a different approach by incorporating testing-support artefacts (called test contracts) at the model-based specification level to improve model-based component testability with model-based test contracts. They believe that modelbased testability stands at a testing level above traditional code-based testability, and thus is consistent with and supports model-based approaches to SCT (Zheng & Bundell, 2008).

Quality Assessment and Quality Improvement for UML Models
The ISO/IEC 9126-model defines no uses, but distinguishes between internal quality, external quality and quality-in-use. The quality ISO/IEC 9126-model is a generic quality model that covers internal and external quality in one abstract model. The model for quality-in-use is similar to the operation use of the McCall model. However, quality-in-use and external quality are out of the scope of this paper, and therefore not discussed any further (Jalbani, 2011). J u l y 1 5 , 2 0 1 3

Comparative evaluation
In this section we evaluate the above model testability approaches. We declare the achievement and main issue of each approach.

Conclusion
This paper has aimed to provide an overview and compare recent progress in model testability. We study and survey several approaches. But we cannot claim that these approaches are comprehensive and exhaustive. Finally, we have comparison table with different columns that compares all the approaches. The main problem with most of these approaches to testing is considering the behavioral architecture in model testability. It should be noted that although the above comparison is conducted based on some prominent approaches, the outcome of this research is not restricted to such approaches. In other words, my considered criteria either can be served as features to be included in a newly developing system or may be applied to help generally evaluating or selecting model testability approaches. However the results of my comparison show that there is no single superior model testability approach in all cases. Therefore, deciding which approach to use in a certain scenario should be done based on its specifications and combine and present the new approach that is more comprehensive and mature is my future work.

Acknowledgement
This project is sponsored by Ministry of Higher Education (MOHE) in corporation with Universiti Teknologi Malaysia, Research Management Centre (UTM-RMC) under Vote No: 03H74. The authors also would like to thanks those who are directly or indirectly involved in this project.


extfieldsofstudy:
Computer Science
Medicine

text:
Use of a group concept mapping approach to define learning outcomes for an interdisciplinary module in medicine

Learning outcomes are typically developed using standard group-based consensus methods. Two main constraints with standard techniques such as the Delphi method or expert working group processes are: (1) the ability to generate a comprehensive set of outcomes and (2) the capacity to reach agreement on them. We describe the first application of Group Concept Mapping (GCM) to the development of learning outcomes for an interdisciplinary module in medicine and engineering. The biomedical design module facilitates undergraduate participation in clinician-mentored team-based projects that prepare students for a multidisciplinary work environment. GCM attempts to mitigate the weaknesses of other consensus methods by excluding pre-determined classification schemes and inter-coder discussion, and by requiring just one round of data structuring. Academic members from medicine and engineering schools at three EU higher education institutions participated in this study. Data analysis, which included multidimensional scaling and hierarchical cluster analysis, identified two main categories of outcomes: technical skills (new advancement in design process with special attention to users, commercialization and standardization) and transversal skills such as working effectively in teams and creative problem solving. The study emphasizes the need to address the highest order of learning taxonomy (analysis, synthesis, problem solving, creativity) when defining learning outcomes.

creative problem solving. The study emphasizes the need to address the highest order of learning taxonomy (analysis, synthesis, problem solving, creativity) when defining learning outcomes.
Keywords Group concept mapping Á Interdisciplinary learning Á Medicine

Introduction
Clinician-mentored biomedical device design modules are well established and have a proven track record of commercial project outputs and follow-on research [1,2]. Undergraduate medical and engineering students enrolled in the interdisciplinary biomedical design module at University College Cork (UCC, Ireland) are taught biomedical device design-targeted knowledge and problem solving skills, and participate in clinician-mentored team-based projects that prepare them for today's multidisciplinary work environment [3].
Learning outcomes describe what a learner is expected to know, understand and be able to do after successful completion of a process of learning [4]. Learning outcomes (LOs) are part of an international move away from traditional university teaching methods which focused primarily on the student's ability to absorb knowledge. Outcome-based teaching and learning focuses on the equally if not more important student ability to put knowledge to use in solving problems, and operating effectively in a chosen field [5]. Development of LOs is now standard practice in higher education. Various methods are used to facilitate definition of specific module LOs from experts and students such as survey-based questionnaires [6], the Delphi method [7], student self-assessments [8] and expert working groups [9,10].
Constraints associated with standard means of reaching group consensus with respect to defining LOs are: (a) generating a comprehensive set of LOs, and (b) reaching agreement on them. Agreement on LOs (and how much emphasis should be placed on each one) may be even more difficult to achieve when participants represent different professional domains such as medicine and engineering.
One solution to the issues just mentioned is to use group concept mapping (GCM) [11,12]. This research methodology, while building on the strengths of other structured consensus building methods such as focus groups and the Delphi method, mitigates some of their weaknesses. In contrast to the Delphi method, in GCM there is only one round of data structuring as the participants work independently and anonymously of each other to limit the possibility of 'groupthink' or 'peer pressure'. Unlike interviews and focus groups, GCM does not rely on pre-determined classification schemas. The method does not need inter-coder discussion to come up with an agreement. When sorting the statements into groups, the participants, in fact, 'code' the text themselves. Multivariate statistical analysis then aggregates the individual coding schemas across the participants. Consensus is not forced, but emerges organically from the data. This paper describes the first application of GCM towards generation of LOs for an interdisciplinary module in medicine and engineering.

Methods
The project consortium was composed of academic members from medicine and engineering schools at three EU higher education institutions (University College Cork, Ireland; Open Universiteit Nederland, Netherlands; and Katholieke Universiteit Leuven, Belgium). The GCM procedure consisted of five phases: (1) idea generation (brainstorm) and idea pruning, (2) sorting of ideas into groups, (3) rating on two values ('importance' and 'difficulty to achieve'), (4) analysis of the data and (5) interpretation of the results. Project members were provided with a webbased link to a web-based tool for data collection and analysis (Concept System Global 2012). They were asked to generate ideas completing the following trigger statement: 'One specific learning outcome of the Biomedical Design module is…….'.
The resulting list of ideas was then made available to a smaller expert group comprising project members from each discipline and partner institution, firstly for the sorting of ideas into categories (based on similarity in meaning), giving names to the categories, and secondly for the rating of the ideas on two values-importance to achieve and difficulty to achieve. Data analysis included multidimensional scaling and hierarchical cluster analysis (HCA) for sorting of data, and means, standard deviations, and correlations for rating of data.

Results
Nineteen experts from the consortium responded positively to the invitation to participate in the study. Sixteen members contributed to the idea-generation phase, nine to the sorting phase, and seven to the rating phase.

Clustering results
The first step in the GCM data analysis is clustering. An important representation validity estimate here is stress value. It reflects the goodness-of-fit, i.e. how accurately the concept map represents the way the participants structured and organized the information. The stress value of this GCM study was 0.28, which is the same as the average stress value reported in a meta-analytical study of 69 GCM projects [13]. Clustering uses multidimensional scaling (MDS; assigning each statement a bridging value, which is between 0 and 1) to position the learning outcome statements. HCA was employed to cluster groups of LOs. Several clustering solutions were checked, applying the practical heuristic' 20-to-5 0 . This means we started from a 20-cluster solution with the goal to arrive at a 5-cluster solution.
The next step was to attach meaningful labels to the clusters. There are three GCM methods available for labelling. The first method is to check what the system suggests. This means that the system suggests a label for a group of statements, based on the label given by a group member whose centroid is the closest to the centroid of the cluster formed by the aggregation of the data from all the members. The second method is to look at the bridging values of the statements composing the cluster. The Group concept mapping and medicine 247 statements with lower bridging values typically represent a cluster better. The third method is to read through all the statements in a cluster and to define in a label what the story is behind the learning outcome statements (what does the cluster want to tell us?). To define the cluster labels for this study (e.g., collective theme of the statements, or category) we combined all three methods. The following clusters were identified: (1) Attention to end user is about the need to take the characteristics of biomedical design end users (doctors, nurses, patients) into account. (2) New approaches emphasizes the need to look for new design methodologies, include results from design research, and implement original ideas in designing medical devices. (3) Design process refers to knowledge and skills related to conducting highquality design activities, from need assessment to developing and testing working prototypes. The average bridging value among the clusters was 0.37. High coherence within a cluster (lowest bridging values) means that the most people agreed on the LOs. This applies to the clusters 'higher order skills' (0.03), followed by 'learning goals' (0.10), 'problem solving process' (0.18) and connecting domains (0.20). The clusters with the highest bridging values were 'regulation and ethics' (0.71) and commercialization' (0.70).

Rating results
The GCM system provides a visualization of the expert group rating results. High rating results are depicted as high numbers of cluster layers. Figure 1a, b depict the layers representing the rating category outcomes 'Importance to achieve' and 'Difficulty to achieve'. Pearson's product-moment correlation coefficient test showed a moderate correlation between both measures (r = 0.52, p \ 0.001).

Discussion
The GCM analysis shows that 'higher order skills' and 'communication' are the two most important clusters of interdisciplinary LOs. However, these outcomes also require the most effort before they can be achieved. The clusters 'learning goals', 'problem solving process' and 'connecting domains' also contain outcomes that are perceived by the group to be difficult to achieve. The least important cluster from the expert group analysis was 'commercialization' and the cluster 'regulation and ethics' was considered to contain outcomes that were easy to achieve. This GCM framework reveals not only LOs related to traditional topics such as 'design process' and 'creative problem solving', but also draws attention to educational outcome themes such as 'commercialization', 'standardization', 'regulations', and 'ethics'. The results suggest emphasizing elements of the highest levels in learning taxonomies by defining LOs such as 'analysis', 'synthesis', 'problem solving' and 'combining knowledge from different professional domains' for either informing the design process (e.g., implementing recent developments in software design to the biomedical design process) or stimulating creativity (e.g. creative strategies of 'looking in other worlds', 'making novel combinations' and 'connecting the unconnected').

Validity and reliability considerations
High values for GCM on internal validity and reliability estimates were reported in a recent meta-analysis, where quality and rigour of GCM was compared with other mixed participative methodologies [13]. One important validity criteria is how well the mathematical model produced by multidimensional analysis (MDS) and HCA reflects the judgements of the participants in the study. To estimate an acceptable level on the stress index in GCM studies, the authors of the meta-analysis refer to a simulated study [14]. Here 500,000 matrices were calculated with 100 objects scaled. Results showed that for two-dimensional multidimensional (MDS) solutions where 100 objects have been scaled, there is a 1 % chance the arrangement of the objects in the matrix is random if the stress value is below an upper limit of 0.39. The stress value of 0.28 for this study is considered a very good estimate for the internal representation validity of this study given the small sample size.
Criteria for external validity of GCM studies require involvement of independent experts with different perspectives on the issues at hand, a variety of methods for data collection, and the extent to which the brainstormed statements reflect the reality as constructs and scope. Our study included experts with educational backgrounds in engineering and computer science, medicine and healthcare, social sciences, maths and science and business and management. In the instruction for idea generation, we explicitly advised the participants to brainstorm ideas and also to refer to information in dedicated written sources-journals, books, reports, blogs or personal communication with other experts. The final list contained 86 ideas. We are not aware of any other study on LOs that has produced such a large number of ideas. When presented with the final cluster solution, our participants acknowledged that the list of ideas was comprehensive, that the concept map reflected the way they had structured the information and that the analysis generated an even richer picture than they were expecting.
In the present study, the number of contributing consortium group members in the sorting and rating activities was low. However, given the acceptable study stress value of 0.28 and considering that studies in other professional domains (usability) [15] claim that there is a 0.75 correlation between the results from five participants and ultimate results, we believe that multidimensional scaling using the sorting data from nine people produced an accurate picture.

Conclusions
Our GCM study identified content areas related to biomedical design module LOs which can be grouped into two main categories: technical skills (new advancements in design process with special attention to users, commercialization and standardization) and transversal skills such as working effectively in teams and creative problem solving.
This study provides not only an empirical basis for depicting the main learning outcome areas, but also suggests how to operationally define them (through the statements in each cluster). It emphasizes the need to address the highest level of learning taxonomy (analysis, synthesis, problem solving, creativity) when defining LOs. The same methodology can be applied to address various issues related to medical education: from defining LOs within different medical discipline modules to classifying different teaching techniques. The GCM method is particularly useful for defining LOs within the growing number of interdisciplinary modules offered at undergraduate level, stemming from recommendations to foster transferable skills such as communication, teamwork, time management, critical thinking, and research specific skills [16][17][18].