On Tue, Apr 11, 2023 at 12:40:19AM +0800, Alan Huang wrote: > Hi, > > I am reading section 6.5.4, there is one paragraph said: > > > The fraction of cells visited by PWQ is similar to that of SEQ. In addition, PWQ’s solution time is greater than that of PART, even for equal visit fractions. The reason for this is shown in Figure 6.28, which has a red circle on > > Figure 6.29: Effect of Compiler Optimization (-O3) > > each cell with more than two neighbors. Each such cell can result in contention in PWQ, because one thread can enter but two threads can exit, which hurts performance, > > I don't know why there is competition only when a cell has more than two neighbors? If there are only two neighbors, PWQ won't create another thread, so there will not be contention. In that case, PWQ will have the same thread exit the cell that entered it. Only when there is more than two neighbors will PWQ create additional threads, which can then contend with the original thread and with each other. > And as the subject said, what does "one thread can enter but two threads can exit” mean? Let's start in the upper left-hand corner of Figure 6.28. The first cell has only one neighbor, namely the one beneath it. So PWQ just advances to that cell without contention. But the next cell down has two exits, so PWQ will create an additional thread, one heading right and the other heading down. Now contention is possible. > After checking the code(maze_fg.c), Doesn’t every cell in the maze can result in contention? You mean (for example) from a thread on one side of a wall suffering memory contention with a thread on the other side of that same wall? If so, yes, but that can only happen if some earlier cell had more than two exits. Suppose that we had a boring maze that had no cells with more than two exits, so that only one path was possible. In that case, there would only be one thread throughout, so no contention. Or am I missing your point? Thanx, Paul
