keeping simple

Category: Uncategorized

  • Doing it wrong: Poul-Henning Kamp

    Kamp writes to explain that virtual memory behavior can be important for program performance. That is, he explains

    From the programmer’s standpoint, the working set of information is the smallest collection of information that must be present in main memory to assure efficient execution of his program.

    But that note is actually from Peter Denning’s classic article (http://portal.acm.org/citation.cfm?doid=363095.363141 and http://cs.gmu.edu/cne/pjd/PUBS/WSModel_1968.pdf ) published in 1968 in Communications of the ACM – the same publication in which Kamp’s article appeared more than 40 years later. Kamp’s main result is that a search algorithm over a very large set of objects will perform poorly if it encounters a large number of page faults (if the working set is too large for the physical memory allocated to the process)!  The publication of Kamp’s article in ACM Communications shows something about the culture of computer science as an academic field these days.

    At least Kamp is doing some performance analysis and measurement – things that are definitely out of fashion in the field.  And he cares about performance.

    What good is a O(log_2(n)) algorithm if those operations cause page faults and slow disk operations? For most relevant datasets an O(n) or even an O(n^2) algorithm, which avoids page faults, will run circles around it.

    Indeed.

    A classic blunder in optimization was committed some years ago by one of the major software vendors. We had their first interactive timesharing system, and it was a “learning experience” in a variety of ways. One such experience was that of the FORTRAN compiler group. Now any compiler writer knows that the larger the hash table you use for a symbol table, the better your performance on lookup will be. When you are writing a multipass compiler in a 32K mainframe, you end up using a relatively small symbol table, but you create a really, really good hash algorithm so that the probability of a hash collision is reduced (unlike a binary seach, which is log n, a good hash table has constant performance, up to a certain density, so as long as you keep the density below this threshold you might expect that you will typically have an order 1 or 2 cost to enter or lookup a symbol, on the average. A perfect hash table (which is usually precomputed for constant symbols), has a constant performance between 1.0 and 1.3 or thereabouts; if it gets to 1.5 you rework the hashing to get it lower). So anyway, this compiler group discovers that they no longer have 32K, or 128K, or 512K. Instead, they now have a 4GB virtual address space. “Hey, let’s use a really big hash table!” you can hear them saying, “Like, how about 1 MB table?” So they did. But they also had a very sophisticated compiler technology designed for small and relatively dense hash tables. So the result was that the symbols were fairly uniformly distributed over the 256 4K pages in that 1MB, which meant that every symbol access caused a page fault. The compiler was a dog. When they finally went back to a 64K symbol table, they found that although the algorithm had poorer “absolute” performance from a purely algorithmic viewpoint (taking many more instructions to look up a symbol), because it did not cause nearly as many page faults, it ran over an order of magnitude faster. So third-order effects do matter. http://www.flounder.com/optimization.htm

    You also have to worry about that constant factor hidden in the Big-O notation.

    Basic knowledge in computer science keeps being lost. There is no culture of measurement, education ignores “low level” technology, and engineering methodologies are discarded.

  • Process algebra reconsidered

    Paper is here.
    The following incorrect claim is not unusual in the process algebra literature.

    Basically, what is missing [in classical automata theory] is the notion of interaction: during the execution from initial state to fi nal state, a system may interact with another system. This is needed in order to describe parallel or distributed systems, or so-called reactive systems. When dealing with interacting systems, we say we are doing concurrency theory, so concurrency theory is the theory of interacting, parallel and/or distributed systems.[Bae05]

    Actually a sophisticated notion of state machine product was developed for representing composition of “interacting” state machines starting in the 1950s[HS66]. A general survey can be found in a monograph by Gecseg[Gec86], Domosi provides a more modern, more algebraic treatment [DN04] and [Yod09] provides practical techniques for construction of complex products.
    […]
    The reader familiar with the process algebra literature will note that such an e ffort must find a way to model the non-determinism that is so fundamental to the process algebra world-view. Since deterministic programs are used to produce pseudo-random number sequences and to model Brownian motion and even the stock market (perhaps not the best example at this date) the problem is easier to solve than it appears at fi rst. Section 4 will include a short discussion on the diff erence between “real” non-determinism and simulated non-determinism, but certainly there is nothing in the basic axiom set of Milner’s original process algebra that notices this distinction as far as I can see.

    To read more see the paper.

  • More state diagrams

    Length 5 queue

    An and-gate with 2 state delay
    and gate delay 5 ATT TwoPi rendering

  • How much should software cost?

    The biggest VA outlay — and its biggest savings generator — was the Vista’s Computerized Patient Record System, the home-grown system for electronic health records that was found by the study to cost $3.6 billion. Other IT networks for administering medications with bar codes, picture archiving and communication systems and the Laboratory Electronic Data Interoperability application together cost $470 million.

    Lots of money. Result – you can predict this right? Big government bureaucracy. Massive billion dollar software development project.  And the result is:

    The bottom line: “We conservatively estimate that the VA’s investments in the four health IT systems studied yielded $3.09 billion in cumulative benefits net of investment costs by 2007,” say the authors, a team from Center for IT Leadership at Partners Healthcare in Charlestown, Mass. The results looks at measures such as reduced workloads, freed workspace and savings from items such as unneeded medical tests and avoided hospital admissions.

    Ok. One should cultivate skepticism of such studies, but it is interesting. The system, by the way is not open source – it is public domain. And it’s based on the venerable MUMPS so there, all you language purists. Look at this code fragment, from the Wiki entry, and weep.

    %DTC
%DTC ; SF/XAK - DATE/TIME OPERATIONS ;1/16/92  11:36 AM
     ;;19.0;VA FileMan;;Jul 14, 1992
     D    I 'X1!'X2 S X="" Q
     S X=X1 D H S X1=%H,X=X2,X2=%Y+1 D H S X=X1-%H,%Y=%Y+1&X2
     K %H,X1,X2 Q
     ;
C    S X=X1 Q:'X  D H S %H=%H+X2 D YMD S:$P(X1,".",2) X=X_"."_$P(X1,".",2) K X1,X2 Q
S    S %=%#60/100+(%#360060)/100+(%3600)/100 Q
     ;
H    I X<1410000 S %H=0,%Y=-1 Q
     S %Y=$E(X,1,3),%M=$E(X,4,5),%D=$E(X,6,7)
     S %T=$E(X_0,9,10)*60+$E(X_"000",11,12)*60+$E(X_"00000",13,14)
TOH  S %H=%M>2&'(%Y#4)+$P("^31^59^90^120^151^181^212^243^273^304^334","^",%M)+%D
     S %='%M!'%D,%Y=%Y-141,%H=%H+(%Y*365)+(%Y4)-(%Y>59)+%,%Y=$S(%:-1,1:%H+4#7)
     K %M,%D,% Q
     ;

  • Notes on modularity

    Modularity is a desirable but elusive design property for large scale programs and computer systems [10, 11]. Designs that appear modular may, once put into practice, actually turn out to be example of  “false modularity” because of interdependencies between components. For example, the apparently modular architecture of micro-kernel operating systems [9] has run into practical difficulties [6, 3]. Examining how state machines can be constructed by connecting simpler state machines together, provides some insight into why real modularity is so powerful and how to avoid false modularity. In this paper, I’m going to sketch out how to look at modularity from the perspective of state machines, try to derive a few “rules of thumb”, and point to some of the deep mathematical basis of this method.

  • Power savings via software

    This press release is particularly fluffy, but whatever the reality of this very vaguely defined algorithmic development the basic message is correct

    to validate nine terabytes of data (nine million million or a number with 12 zeros) in less than 20 minutes, without compromising accuracy.  Ordinarily, using the same system, this would take more than a day. Additionally, the process used just one percent of the energy that would typically be required.

    The way to reduce power use in data centers is to improve the ratio of  (useful clock cycles)/(overhead + idle clock cycles) and to optimize I/O.

    But this requires a 100% change in the way that software is designed from the current method.

  • Queues and algebra

    Suppose we have a state machine Q, that implements a common first in first out queue. The input alphabet of Q consists of “Deq” and “Enq x” where “x” ranges over a set of values, say, V. Let’s fix the max length of Q at some constant k. As usual, given a sequence of events “w”, write Q(w) for the output of Q in the state reached by following “w” from the initial state. For the empty string NULL, define Q(NULL)=(). If a=Deq then define Q(wa) depending on Q(w) – if Q(w)=() or Q(w)=(x) then Q(wa)=(). If Q(w)=(x1 .. xn) then define Q(wa)=( x1 …). If a=Enq x then if Q(w)=() define Q(wa)=(x), if Q(w)=(x1 .. xn) where n<k define Q(wa)=(x,x1 … xn) and otherwise leave Q(wa)=Q(w). The number of states of Q is a function of the number of elements of V and the constant k and grows rapidly as they grow – sum[i=1, k](|V|^i  ).

    If you visualize the graph of Q, you can see it contains non-trivial loops – which means that the monoid associated with Q contains groups. The advantage of decomposing Q into a product of smaller machines is that this might guide a smarter implementation. Well, I’m kind of cheating here, because programmers have found a variety of smart implementations that do strip out the group structure.

    The easy decomposition produces two counters, and a collection of k storage elements that are loop free state machines: an input “store x” moves the machine to a “x” state. They do contain loops but only trivial ones. The counters are group machines. We number the storage cells 0 to k-1.  We can have one mod k counter that “points” to the tail of the queue and one that counts the size of the queue. On an enq operation the enqueued value is stored in the storage element identified by subtracting the size from the tail mod k,   and the size is increment mod k+1. An enq operation when the size=k is ignored and has no effect. On a deq, the size is decremented and the tail is incremented by one mod k+1. What we’ve done is construct a system in which the state machine monoids are two cyclic groups and k-aperiodic monoids. If we then switch to more complicated data structures, like ordered lists, it’s not that hard to see how a permutation group might be used to manipulate pointers to a pile of storage locations. For example (n1,n2,n3,n4,blank, n5,n6) might be an ordered list with n5 and n6 being free. An enqueue would generate some shuffle to say, (n1,n2,n5,n3,n4,blank,n6) and then a dequeue would produce (n2,n5,n3,n4,blank, n6,n1).

    A nice property of groups is that “undo” always works. So if the data in the storage elements can be marked in some way, a deq or enq can be undone by subtracting mod k or permuting backwards.

  • simple lemma about pipelines

    The connection between group structure and pipeline design seems like it merits a lot more attention than it gets. It’s not too hard to show that in a pipeline like the one to the right, the induced monoid of M1 must be a homomorphic image of the composite state machine. This immediately brings in the limiting factors of simple groups.

    KR theory is too vague though. For example, I’d like to know something about the relationship of M and M’ in the case that the induced monoids are isomorphic. They definitely do not have to be the same, but seems like they should be similar enough so that changing the output map would equalize.

  • The Amory Lovins bottleneck

    Lovins observes that power inputs in many industrial processes go into a bottleneck that makes power conservation hard if you start at the wrong end.  The power goes into a long pipeline of process that emerges on the other end with some useful (in theory) work. If you start on the power input end, then reducing power x% requires percolating incremental improvements down the chain of linked machinery with each step reducing work at the step further down the pipeline. But if you start on the other end, changes automatically flow upward. The same, obviously, holds true for data centers. If you start by improving power efficiency of air-conditioning – a good thing in itself – you cannot obtain the scale improvements that can be gained on the other end of the pipeline by reducing the activities that use power and generate heat. That is, if you can increase work-done/computational-steps you drive savings up the pipeline. And the kind of large scale savings Lovins achieves in other industrial processes seem plausible: if you reduce power demand at the work end enough to reduce the inputs of cooling needed so that a smaller air conditioning unit can be used, you have a potentially greater savings than by improving the efficiency of the air conditioning unit.

  • Instructions per joule – a good start

    … multi-GHz superscalar quad-core processors can execute approximately 100 million instructions per Joule, assuming all cores are active and avoid stalls or mispredictions. Lower-frequency in-order CPUs, in contrast, can provide over 1 billion instructions per Joule—an order of magnitude more efficient while still running at 1/3rd the frequency. Worse yet, running fast processors below their full capacity draws a disproportionate amount of power:

    Dynamic power scaling on traditional systems is surprisingly inefficient. A primary energy-saving benefit of dynamic voltage and frequency scaling (DVFS) was its ability to reduce voltage as it reduced frequency [56], but modern CPUs already operate near minimum voltage at the highest frequencies. Even if processor energy was completely proportional to load, non-CPU components such as memory, motherboards, and power supplies have begun to dominate energy consumption [3], requiring that all components be scaled back with demand. As a result, running a modern, DVFS-enabled system at 20% of its capacity may still consume over 50% of its peak power [52]. Despite improved power scaling technology, systems remain most energy-efficient when operating at peak utilization

    Andersen, D. G., Franklin, J., Kaminsky, M., Phanishayee, A., Tan, L., and Vasudevan, V. 2009. FAWN: a fast array of wimpy nodes. In Proceedings of the ACM SIGOPS 22nd Symposium on Operating Systems Principles (Big Sky, Montana, USA, October 11 – 14, 2009). SOSP ’09. ACM, New York, NY, 1-14. DOI= http://doi.acm.org/10.1145/1629575.1629577

    Once you start thinking about instructions/joule, you need to also think about work/instruction. This number is going to make current system look a lot worse than even the dismal summary above because the immense amount of overhead is so overwhelming. It’s not even just OS and Virtual machine overhead, as horrible as that it. Consider a Java program. Anyone who has ever looked at production Java code can testify that the number of layers of “frameworks” and “libraries” and so on between a program and actual computation is not small. So consider a program that reads data from the network, processes, stores in a DB, and sends responses. This is not an unusual program model. Ok: we begin with an interrupt that must navigate the virtual machine layer to some OS that most likely contains code that replicates most of the functionality of the VM layer, then  layers of protocol fiddling, the sad fumbling over locks in the a “fine grained locking” OS, the clumsy process model and atrocious scheduling left over from the days in which CPUs were scarce resources, the IO layer (DEAR GOD!!), the pointless copying of every bit of data over and over again, and then the agonizingly bumbling progress of the intent of the programmer dripping down through geological layers of Java to a byte-code interpreter – and that’s just the start of this slow motion avalanche: electric power is being converted into waste heat with appalling recklessness.

    I’m not sold on the “Fawn” model, but the problem analysis is right on the button.