Thanks Kenneth. Excellent example. I didn't consider that the load for the counter must be first to cause the serialization.
Jon Perryman. >________________________________ > From: Kenneth Wilkerson <redb...@austin.rr.com> > > > >I have used PLO almost exclusively for serialization in multi-address space, >multi-du code for almost 10 years. I use all 6 operations. Since everything >I write is 64 bit mode, I generally use the +2 variant (64 bit length) but I >like using the +3 variant (128 bit length) for some really cool stuff. As >Rob pointed out, " The key to their use is to have a lock word counter that >the caller increments and then prepares the new values in other regs.". But >I add that the real key is designing the application to use PLO for >serialization which is much more than just writing macros to do the guts of >the processes (though I almost always use macros). > >Consider this example. I have a singly linked chain of 64 bit cell addresses >on quad word boundaries. The chain pointers are a quad word at the start of >the cell. The first double word is the head of the active chain. The second >double word is the head of the free chain. The first quad word of each cell >is a double word pointer to the next active entry followed by a double word >pointer to the next free entry. The chain has a quad word counter on a quad >word boundary. The first double word of the counter is a change count. The >second double word is an active element count. The algorithm always adds new >cells to the head of the list. > >I can add a new cell by using a LMG to load the counters, increment each >counter by 1, compute the new head, compute the old head's new previous and >then use a Compare and swap and double store 128 bit to add the new entry. >Since every update increments the first double word counter by 1, the >process only completes if no other process updated the counter. If the >counter has changed, it needs to re-drive. By adding entries to the head, I >can also have code simultaneously searching the chain while entries are >added. Of course, if the new head is added before the search starts, it >won't be found. But that's no different than using a lock. If the search >acquires the lock before the add, it won't be found either. > >I can even add an element that requires a search for one that has already >been added. In this case, I load the counters before the search. I search >the chain. If not found, I increment the counter and perform the add. If the >add fails, I have to re-drive the search. > >I can also delete entries from the chain. When I find the entry to be >deleted, I save its previous entry. I can adjust the counts, re-compute the >chain pointers and do a Compare and Swap and triple store to delete the >entry and add it to the fee chain. I can still search the chain but I'll >probably need to do a Compare and load to do so. I can avoid the PLO compare >and load by not actually deleting the cell but using the low half byte of >the active next pointer as a deleted flag. But that has disadvantages as >well. This also adds a little more logic to the add, since I now need to add >using the free chain if one exits or an add acquiring a new cell. > >There are a lot of details not given here for brevity. This example also >uses an unordered single linked list to simplify the example. But properly >designed PLO operations can be performed on ordered doubly linked lists as >well. When I read the Principles of Operations on the Z/EC12 transactional >execution facility, I think strongly of a PLO on steroids. The point is that >PLO can almost be used exclusively for serialization. > >As far as overhead, I have done a lot of testing and the key is the proper >choice of the lock word and the algorithm. In my research, the throughput >advantages of PLO far outweigh its overhead. I would love some time with the >transactional execution facility. From my reading, it eliminates the need >for any serialization other than PLO or transactional execution. Though I >understand that IBM has chosen a redrive limit as the determining factor as >to whether to fall back to a lock. > >I believe the only limit to using PLO for serialization is the imagination. > ---------------------------------------------------------------------- For IBM-MAIN subscribe / signoff / archive access instructions, send email to lists...@listserv.ua.edu with the message: INFO IBM-MAIN
