Writing Assembly Language Functions for quad-NA

VECTOR Vol.7 No.4

Writing Assembly Language

Functions for DNA

by Allan Gay

Look. I know the Reverend. I’ve read his sermons on GNA in Vector and trembled. 1 mean, don’t get me wrong - I'm a religious man myself - but I prefer to do my crusading in carpet slippers and with a good book in hand. Well - not that Good Book exactly. Not APL2 Programming: System Services Reference for heaven's sake!

Sigh.

Tm not making much sense, am I? I suppose I’d better start at the beginning.

an ancient Programmer and he stoppeth one ... Evening was drawing in and I was sprawled chair with my heels up on the mantelpiece, toasting the old buns, when the phone rang. With one convulsive leap, I switched off the budgie, catapulted myself to the desk and snatched up the handset before the second ring. Hi , I said, as nonchalantly as I could manage.

My son,” said a voice, how dost thou fancy writing some [NA Assembler functions for APL2?” It was the Reverend.

Well, it sounded like work and you know me and work (I could watch it for hours, etc.) But annual fitness rating was imminent and I knew the Reverend was big in the Synod, so I gave his challenging (read gruesome) proposal the big hello. Your Grace,” I said, you know me and work”,

I thought he sniffed, but it may have been line noise. Thy mission - shouldst thou choose to accept it - is to produce three partitioned functions, namely Or Reduce, Or Scan and LessThan Scan. They will be dyadic, handle only Boolean vectors and will produce Boolean vector results. And,” he said, one assumes thou wilt also supply a FirstGroup routine if time permits.”

Next morning, I tried some deep thinking but it was no good. Id already taken compassionate leave to bury every elderly aunt which IT possessed - some of them three times - and there had been barbed comments in the office of late

100

VECTOR Vol.7 No.4

about the ongoing reduction in the population of northern England. It had to be faced: I was cornered.

So I dug out a pile of old hymnals, fired up the Shareware 370/ Assembler simulator on the old PS/2 and did some heavy coding. The Reverend seemed to be looking for some pretty startling reductions in CPU time and I for one wasn’t going to disappoint him.

Piece of cake ... Well, you know, after reading an old sermon or two, dashed if things seemed all that bad. I'd a fair idea of what the inputs and outputs would have to look like in CDR format, the interface details between APL2 and me seemed a pretty straightforward piece of groined cross-vaulting apart from the odd ECV or so, the actual logic to do the bit manipulations would all be done in the cathedral organ’s registers for reasons of speed and tone quality and - most important - [had faith.

So, when I presented myself at the tradesman’s couple of days later I was feeling pretty holy. I had the relevant tracts with me, the Assembler prayers were on diskette and all in all I thought it was going to be a piece of cake.

While [ used a magnetic card at the holy water vending machine in the south transept, an acolyte asperged and fumigated my diskette and checked it for impure thoughts. Then the prayers were copied into the bowels of the cathedral organ and battle commenced.

Now I don’t know if you've ever groped blindly down a drain in an attempt to pick up a lead weight with a piece of limp string and a sweaty sock. Take it from me, the TSO TEST facility isn’t like that at all. Heavens no! When you are running APL2 under TEST, it’s more like using a B-52 to strangle a chicken. What I mean is there’s a strong chance that you'll overshoot the target area and have to go round again. And that’s no joke after a 7,000 mile flight from the initial! LOAD command, believe me.

I had some initial troubles. 1 admit that. But I knew that once Id decoded the cryptic words of my guide, the aforementioned System Servi es Reference, I'd crack the interface and it would be all plain sailing. After all, the algorithms were implemented entirely within the registers. I mean, what could possibly go wrong with that?

The troubles mounted until, after two days, I came to doubt that my guide was - how shall put it? - strictly au fait with all the nuances. I based this suspicion on

101

VECTOR Vol.7 No.4

the fact that whenever I followed its advice my prayers, instead of winging heavenwards, tumbled on the mat with their paws in the air. Consequently, it came as something of a relief to learn from the Reverend that my guide had been excommunicated in 1987. Yes, the true faith was being expounded nowadays by APL2 Programming: Processor Interface Reference and, with its help, I got my prayers to implement FUNCTION linkage (the fanciest, detailedest and most sanctified type) to the point where they were returning explicit APL results at last.

The real stuff... Now at this point, some of you fellow pilgrims out there will want to know the magic formula. Frankly, it seems pretty unfair that you chaps should be purified by my suffering but, heck, I’m going to tell you. services, and I don’t mean Matins. The services I’m talking about are the interpreter’s VP, VQ, XC and XG services. Look, will someone at the back push the kids and those crazy BASIC fans out of the room? This is grownups’ talk. Thanks.

Okay, here’s the real stuff. First off, every time the APLer runs the name- associated function, we get called with normal MVS parmlist hanging off register 1. Dangling off the parmlist, there are pointers to the System Services routine, the ECV, and a gash, zero-filled, persistent doubleword which can be used to remember things between successive runs of our function.

It’s good style to be re-entrant so that we can serve multiple communicants from the one chalice. Of course, cutting down on the crockery means we've got to watch the hygiene aspect. We aren’‘t allowed to modify ourselves, so we can’t < in our routine but must instead acquire storage for them dynamically. We use ... *’P service for this and APL2 makes it easy for us by bolting a VP parameterlist into the initial parameterlist. Just pop in the byteage required, call System Services and bingo! After VP has delivered the goods by giving us a slice of the area reserved by APL2's FREESIZE parameter, we store the slice’s address into the gash doubleword. Every time we're called, we check the current instance of that doubleword. If it’s zero, we do a VP; if it’s not, we use it to reach the area we acquired in a previous life. We may not be able to take it with us, but we certainly can get it back afterwards; our camel slinks around the eye of the needle.

Whenever we get called, there’s a request code in the ECV to tell us what's going on. If it’s a delete-linkage request and we an area from VP, we use the VQ service it and then we grab a couple of hotel towels, use our credit cards and check out. The holiday is over. This is either because the APLer has

102

VECTOR Vol.7 No.4

just )OFFed because he has severed our name association. Otherwise, it’s a function-linkage request, meaning the APLer is on the blower and there’s work to be done.

Although I’ve just given you the goods on getting and managing work area, I wouldn’t like you to think I knew it all along. Golly, no! I’d read and misunderstood a remark to the effect that storage acquired via VP is automatically reclaimed when the process terminates. Believing, erroneously as it turned out, that my prayers were processes within the meaning of the act and that termination meant returning control to APL2, initially refrained from any use VQ service, I use the gash doubleword to remember where my area was. Instead, assuming that each previous execution’s storage had been released, I blithely requested storage afresh at each invocation of my prayers. The eventual effect was to consume all the freespace and wreck the application.

You at the back ... Right, I'll pause here and take a few questions. You, sir. Whassa what? Whassa ECV? Thassa big control block which contains all sorts of information about the function arguments, together with a parameterlist for the XG service and various items of session info. Using its contents in conjunction with the XC and XG services, we can input arguments, get room workspace for the result and, when we've constructed it, return it to APL by connecting it to this ECV.

Whassa CDR, did I hear you say? That stands for Common Data Representation and it’s just the descriptive information for an APL variable. You know, its rho, rank, type, and so forth. By examining CDR, we can find our way to its data and also know how to interpret that data when we get there. It can get ptetty complex but there are ways of forcing input variables into a straitjacket so that we don’t have to program every conceivable possibility. My prayers handled Boolean vectors exclusively. We also have to construct a CDR for our result variable.

Yes, madam? How do you find out about the ECV’s format? There are diagrams in the Processor Interface Reference and there’s an AP2ECV macro which maps it and gives mountains of documentation. Speaking of macros, you should all note that there’s an AP2CDR macro, too. You'll probably find those macros in an APL2.AP2MACS library on one of the DLIBs; check with the and if I suddenly start to speak in tongues, the first three letters of each word will be CDR or ECV and you'll know I’m talking about fields defined by the macros.

103

VECTOR Vol.7 No.4

It’s good to see you writing all this down, because there’s going to be a short catechism afterwards.

The moving target ... That covers the working storage aspect, so let's now take a look at creating variables. There are various ways of playing it but I’m just going to tell you the way I did it. You see, there are lots of choices because the APL2 environment isn’t static. As APL objects are created, modified and deleted, things get moved around by the interpreter to reclaim released areas and generally defrag the workspace. This means you can start creating a variable, go back later to wrap it up, and find it has moved elsewhere. Obviously, while your [WA routine is actually running, this doesn’t happen. But, when you make certain calls to the interpreter, any workspace addresses you are currently working with will probably be invalidated. ECVXRLOC contains a relocation count which will have changed if a garbage-collect has occurred.

This mutability aspect is a pest but APL2 gets round it by using tokens. Now when APLers talk of tokens they are usually discussing APL statement parsing, but that’s not what we mean idea that every separately addressable object in the workspace has a unique badge. That means each variable’s descriptor (CDR) and each related data has a unique token which is unaffected by workspace defrag activities. APL2’s XC service exists to supply the current virtual storage address for any valid token we care to supply. APL2’s XG service, which allocates space in the workspace (as opposed to VP, which allocates it in the freespace) returns not only the address of the allocated space but also its token. APL2 can distinguish between addresses and tokens, so you can pass either to APL2 interchangeably. What APL2 will pass to you varies according to circumstances and I preferred to inspect such pointers and find out for myself.

The rule for pointers is: if the high-order bit is on, we have a virtual storage address which we can use as it stands. If the bit we have a token and we need to use XC to equivalent virtual storage address. This finds application when we process the input variables. Their respective CDRs’ tokens reside in ECVXCDRL (left-argument) and ECVXCDRR (right-argument). Within each of those CDRs is a pointer to the argument data.

If you are just creating a simple result, the strategy is straightforward. First, you inspect the input arguments, determine the maximum possible size your result could be, use XG to get a suitably-sized piece of the workspace in which to build the result data, and note its token. Second, you manufacture the data in that area,

104

VECTOR Vol.7 No.4

using the virtual storage address from XG to access it. Third, you use XG again to get more workspace in which to manufacture the result’s CDR. Fourth, you build the CDR and you put the retained token of the data area into CDRPTR, in effect hooking the data to the descriptor. Finally, you put the CDR area’s token into ECVXCDRZ to make the result available to APL2 when you cede control.

Now if you look at that carefully, you'll see that we always complete using one area before we call XG to get another. That means the virtual storage addresses supplied by XG are never invalidated until we've finished using them. And because we retain the tokens supplied by XG, we're able to connect everything together without needing to use XC at all. In fact we don’t even need to look at ECVXRLOC to see whether things have moved, either.

Getting it wrong ... A while back, I observed algorithms were all implemented in the cathedral organ’s registers and I - rather unwisely as it turned out - used the expression piece of cake”. I also asked, rhetorically, what could possibly go wrong with that?” Read on, brothers and sisters! Read on!

When [ at last got the prayers to produce explicit results, [ thought my troubles were over. So when I heard from the Reverend that those results were occasionally wrong I was not at all gruntled. If they had been wrong all the time, I could have handled that, but subtle intermittent errors are bad news. I tried putting the prayers in the fridge for a few hours in case the problems were temperature-related but it was the Reverend who spotted the cause: early bunkout.

Okay, I have a letter here from a listener who asks What the heck is early bunkout for goodness sake?” I won't read the rest of the letter because the style deteriorates and he gets abusive, (cheese it, pal!) but I'd better explain. so, I need to describe the way in which the algorithms were implemented and I also need to explain where we get our performance improvements. Bear with me a moment.

Why and how ... The whole idea of writing these routines was to get things to go faster. If you look at the Reverend’s partitioned functions they are extremely terse but, inevitably, they use several APL2 primitive functions. Those primitive functions don’t know that the Reverend intends to deal only with simple Boolean vectors, so they have to be prepared to field anything that comes along, which means

105

VECTOR Vol.7 No.4

they are overqualified for the job. Also, they produce intermediate results along the way which have to be allocated and deallocated, with the potential workspace defrag at any APL2 is not aware that they are being used to do, say, a Partitioned OR Scan.

Conversely, our Assembler prayers are highly-specific to the expected data, are atomic, and have inside knowledge about the task. Consequently, they are smaller, they have less overhead and they can cheat. (Early bunkout is a form of cheating.) Even better, we can do almost everything in registers and avoid much of the overhead of accessing virtual storage.

The organists among you will know that the top-end IBM cathedral organs have sixteen 32-bit general purpose registers which, unlike those in the 80x86 series harmonium, lack almost all flavour and colour. By this, ] mean that you any of them for almost anything, so there’s a freedom that you just don’t find on smaller instruments. In some of the prayers, I even preloaded constant comparands into spare use within loops. As you can imagine, by eliminating repeated storage fetches of comparands, this expedited comparisons no end.

The basic processing technique, once the input arguments and the output result area had been connected up, was to lope along the inputs 32-bits (a fullword) at a time. Each pass of the loop entailed loading a fullword of left-argument data into one register, a fullword of right-argument data into another, and using register in which to generate result data. Apart from the Partitioned OR Reduce prayer, which could generally be expected to produce a result which contained fewer bits than the input, all prayers produced results of exactly the same length as their inputs. Consequently, at the end of each pass of the loop, another fullword of result bits would be stored in the output variable’s data area.

My big mistake ... Let's take a look at one of the algorithms - Partitioned LessThan Scan - in detail. A LessThan Scan produces a result which is a copy of the input argument in which all onbits except the first have been turned off. Partitioned LessThan Scan does this for each partition in the right-argument input data; the partitions are defined by onbits in the left-argument mask data. For instance:

106010606 041 0 PARTITIONEDLETSCANOi100141411411 o1L10 0010120

106

VECTOR Vol.7 No.4

In this example, the left-argument mask data specifies three partitions of lengths 3, 4 and 2 bits respectively. In real life, however, we're talking about thousands of partitions each of which could be anything from one to thousands of bits long. Because the cathedral organ’s registers go like greased lightning, we can happily loop along, shifting register contents to isolate each bit in turn, inspecting it and deciding what to do with it. We have no alternative. Or do we? The cathedral organ’s repertoire includes many facilities which act on a whole fullword at once.

Imagine what would happen if, having already output the first onbit in the current partition, we loaded the next fullword of left-argument mask data and found it to be all zeroes. It would mean that the current partition continued for at least another 32 bits and, since we'd already output the single onbit permitted for it, we'd have to output 32 offbits. The nature of the corresponding fullword of right-argument data would be completely immaterial. Instead of looping through the 32 bits one at we could zeroed fullword with instruction. This trick of segment-skipping can pay performance dividends when long partitions occur frequently in the input.

What's more, at any time during the processing of a nonzero maskword on a bit- by-bit basis, if a test reveals that all remaining bits are off, we can ignore the remaining dataword bits and store offbits for them in the result. This trick of loop-truncation can pay performance dividends when data onbits are infrequent.

This sort of trickery is the early bunkout to which I previously alluded.

There’s another loop-truncation trick we can play, and this one is where I tripped myself up. Let’s suppose that we've looked at the maskword and we find that there are some onbits in it. This means we've got a new partition starting within the next 32 bits so we can’t do a segment skip. But suppose all the databits were off? We can’t produce onbits in the result if the corresponding databits are off, so couldn’t we store zeroes and bunk out early in that case?

The answer is that we could, but with one important proviso: first we must reset the partition metabit, that status flag which records whether we have yet found an onbit in the current partition’s data. If we were to go into the next partition with the flag still on, we'd produce an all-zero output partition even if the input partition data contained some onbits. Guess who forgot to reset the partition metabit.

107

VECTOR Vol.7 No.4

Connecting things up ... Okay, we're on the homewards stretch now. All that remains is to recount how to make the prayers available to the APLer in his pew and to put some numbers on the resulting CPU-time savings.

The first thing we have to do is to package our prayers as one or more loadmodules. How many we put in a loadmodule is immaterial because the packaging process entails coding and assembling a frontend table which lists all the entrypoints in the individual routines. With this table in place, the usual limit (imposed by the Linkage Editor) of 16 entrypoints within a single loadmodule is eliminated. Instead, the loadmodule ends up with entrypoint via which APL2 enters to look at the table when it wants to name-associate a given function. The number of routines which may be declared in the table is potentially huge.

under discussion, there were only four routines and the application used all four, so they were packaged as a single loadmodule.

To announce each routine to APL2, we create a member in a partitioned dataset termed the Names file. Each member names its corresponding routine and gives a DDname and membername to enable the package loadmodule to be found. Each member also uses a simple shorthand to declare the format of the input arguments and the result. Argument data supplied by the APLer to our functions will be coerced to suit if at all possible; otherwise, a DOMAIN ERROR occurs and we aren't called. This saves us from the chore of writing complex input- validations.

Before starting the application, we preallocate the Names file and the loadmodule library (the latter using the predetermined DDname coded in the Names file members). Then we hook each routine up as an APL function by entering,

'(NamesfileDDname)' 11 ONA function 

After this, the function runs exactly as if it were written in APL. But a lot faster.

The score ... So how did they do? Partitioned OR Reduce was the worst. Overall, it averaged a CPU-time saving of 44%. This means that, on average, for every 100 CPU

108

VECTOR Vol.7 No.4

seconds taken by the all-APL function, the Assembler version took 56 CPU seconds on the same data.

The other three functions did much better. They each saved 92%. Altogether, replacing these four much-loved utility routines knocked nearly 10% off the overall CPU-time cost for the entire application. Since it was a very large and heavily used application, this represented a very substantial reduction in machine costs.

All four functions were pretty much the same size. The average was 870 bytes and the total size of the package loadmodule was 3,592 bytes. The source code per function came to about 320 lines, excluding comments and macro expansions.

Development time averaged about 35 man hours per function. This reflects the learning curve and initial blind man’s buffery. The last function (Partitioned FirstGroup) was taken from inception to completion in only four hours by taking a copy of the Partitioned LessThan Scan function and writing a new logic core, the argument handling and environmental processing being the same. If it’s got Boolean vectors, I’m your man.

The aftermath ... Hosannas ringing in my ears, I totter across close. Back home, curtains drawn, I slump in the gloom with an icepack on my head. The phone rings. Wincing, I lift the handset. Hi , I croak feebly.

My son,” says a brightly enthusiastic voice, how dost thou fancy doing a Partitioned Plus Reduce?” 109