Friday, July 18, 2014

Computing with Graphs

There are a variety of different models of computation. Already in the 1930s there were several models, for example those of Alonzo Church and Alan Turing. The Church-Turing hypothesis proposes that these models don’t differ in the class of computational problem they can solve, at least if the model is rich enough. The set of problems that a Turing machine can solve is the maximal set that any computing device can tackle. The point of alternate models is not to expand that set of computable problems.

It can still be useful to work with other models. A key aspect of any computational model is the way it holds data. A Turing machine uses a tape, a one dimensional array of symbols that can grow in either direction without bound. This ability to store an unbounded amount of data is essential for any computational model to be equivalent to a Turing machine. How to access large amounts of data is a practical challenge for real computers as well as an interesting theoretical issue. A Turing tape gets the job done in very simple way but not in a very practical way. The Random Access Memory that is ubiquitous in modern computers is very practical, but theoretically not very elegant. This inelegance manifests at the practical level in the difficulty of picking the right size for memory address words. Large address words make it easy to access large amounts of data, but are expensive to use. Small address words are efficient but don’t provide the address space needed for complex computations.

My proposal here is to use graphs, of a particular class, to represent the state of a computation. Just like a Turing machine writes new symbols over old symbols on its tape in order to record the result of a computational step, the graph machine will modify a small part of the graph at each computational step.

We have around 70 years of practical experience with computing machines at this point, almost all with Random Access Memory for storing data. How to represent information in a practical way with this graph model, that is a problem that will take years to refine. The starting point is just to explore what works. Bit by bit we can discover the methods that work best.

Could such a radically different computation model ever develop enough through practical experience that it could make any dent in the ubiquity of the Random Access Memory model? My proposal here is for two uses of this graph model. First, it is an interesting model to explore theoretically. The main value I see here is the potential for a more accurate model of memory access times.

Second, it could provide a powerful processor architecture. New compilers for existing high level languages could insulate users from the change in architecture. Processors with this new architecture could certainly be built with existing Random Access Memory components. The greatest impact would be at the level of cache design and virtual memory mapping. This graph architecture is a bit like a hyper-virtual memory. Addresses are never exposed at the processor architecture level! This gives memory mapping huge flexibility. Since the topology of the data is exposed at the architectural level, caching strategies can be vastly more powerful.

This graph architecture is a radical departure from the conventional Random Access Memory, but it could actually be quite practical!

Let us now dive into the details!

The state of computation will be kept as a connected graph, a set of nodes connected by two types of edges: directed and undirected. Each node appears exactly three times in the edges: once as the source of a directed edge, once as the destination of a directed edge, and once at one end of an undirected edge. The entire graph will always be connected, i.e. given any two nodes there will be some way to walk along the edges to get from one node to the other.

Here is an example of a graph that could represent the state of a computation:

This is just like a string of symbols on a Turing tape. To understand what that string of symbols means, or what a graph like this might mean, that requires detailed understanding of the particular computation that is in process. Right now we are just looking at the ways that a computation could read and write snippets of information.

A graph machine would have a set of registers. Probably two registers is the theoretical minimum but a practical number might be the usual 16 or so that are common in today’s processing units. Each register points to some node or other of the graph. Processor instructions would provide operations like:

  • Move register n forward
  • Move register n backward
  • Hop register n across
  • Check whether registers n and m point to the same node
  • Make register n point to whatever node register m is pointing to
By running registers along the edges in various ways and then checking whether they got to the same place, it is easy to determine the shape of any region of the graph.

The general way that computation proceeds is that, depending on whatever aspects of the shape of the graph are important to the computation at hand, one or another graph rewrite operation can be performed.

The first operation is to swap the directed edges between two nodes that are connected by an undirected edge:

This operation can be applied to the example graph above, to yield:

It can then be applied a second time:

The complete graph can be partitioned by the pattern of directed edges. The directed edges will form one or more cycles in the graph. When directed edges are swapped, these cycles can be split or joined. Note that the swap operation can move in either direction along the sequence of graphs in this example.

The second operation is to swap undirected edges between two nodes that are connected by a directed edge:

This can be applied as a next step in our sequence:

And again:

The third and fourth operations expand or contract the graph:

Expansion operations can be applied anywhere on any graph. But contraction operations can only be applied where the proper four node shape exists in a graph, which some graphs may not have at all.

In our example, the contraction operation can be applied:

Now we can alternate, an undirected swap:

a contraction:

an undirected swap:

a contraction:

one more undirected swap:

and one more contraction:

finally arriving at a minimal graph. Note that we could start with this minimal graph and reverse the operations to move in a sequence back to the graph we started with.

We followed a general strategy here to reduce the original graph to the minimal graph.

  1. Swap directed edges to join the directed cycles into one big cycle
  2. Gradually reduce the size of the graph, by repeatedly
    1. Swapping undirected edges to form a contractable four node subgraph
    2. Contracting that subgraph
This strategy thus sketches a proof that these four operations,
  • Swap directed edges
  • Swap undirected edges
  • Contract
  • Expand
provide the capability to move in a sequence from any one graph to any other graph. We can start from any arbitrary graph and reduce it to this minimal shape. We can reverse those operations to construct a sequence from the minimal shape to that arbitrary graph. So a sequence of operations exists to move from any graph to any other graph. Of course in a practical computation one would not commonly move through the minimal graph, which corresponds to a blank Turing tape.

From a theoretical perspective it is useful to explore the power of this pure graphical architecture. From a practical perspective, probably a hybrid architecture will prove more efficient. One could augment the model by adding to each node a word of data, e.g. 64 bits that could be interpreted as a floating point number etc. Floating point numbers could certainly be encoded as shapes of subgraphs, so this augmentation is not theoretically necessary. But this sort of graph-based computation could well prove itself valuable beyond the theoretical context.

Wednesday, July 16, 2014

Energy Needs

How easy is it to supply our typical energy needs? The electric power utilities do that routinely these days. Should we be surprised by that?

There are two pieces to this puzzle. The first: is our typical energy usage a good approximation to our actual needs? The energy we typically use is just what is needed to support our present lifestyle. Many societies, with lifestyles quite different than ours, have survived over many generations on much smaller rates of energy consumption. Do we need to maintain our present lifestyle?

The second puzzle piece: how much energy do we typically use? In the United States, a typical household consumes about 10 kilowatthours each day. Since there are 3600 seconds in an hour, that is 36,000 kilowattseconds, or 36 million joules. How much is that?

To get a feel for it, suppose we wanted to store that energy in a household pumped hydroelectric facility. Suppose we built a reservoir 10 meters high, on top of the roof of the house. How big would the reservoir need to be?

The energy in the reservoir is mgh, where m is the mass of the water, g is the acceleration of gravity, and h is the height of the reservoir. g is about 10 meter/sec^2 and we have h as 10 meter. So 100m = 36,000,000 or m = 360,000 kg. A liter of water weighs a kilogram, so that would be 360,000 liters of water, or about 90,000 gallons.

A typical backyard swimming pool contains about 15,000 gallons of water. I.e. our household hydroelectric reservoir needs to hold about six swimming pools of water in order to supply a day's worth of electricity.

Maybe better not to put that on top of the roof!

Tuesday, July 15, 2014

Against Class Warfare

John Oliver’s recent talk on wealth inequality got me thinking a bit more on the topic. What is the relationship between good government and class warfare? Is government properly an instrument of class warfare? Sometimes government gets corrupted that way, but its proper role is quite the opposite.

Some sort of formal government structure becomes necessary for any society larger than perhaps a hundred families. Very small societies can get away with informal structures. Everyone will know the details of every conflict. The character of everyone else is known and one can understand how to navigate the ambiguities of any transaction. But at a larger scale of society, one regularly interacts with people whom one does not know very well if at all. Some basic framework of assumptions is needed so one can negotiate a transaction without a thorough preliminary investigation being required. It is the job of government to regulate the interactions between individuals so the benefits of larger scale society can be enjoyed.

The fabric of society is woven with relationships of trust. With trust, individuals can interact while giving each other the space for individual decisions. Without trust, one is forced to the extremes of isolation or domination. Warfare is the symptom of the breakdown of trust. Warfare is the symptom of ineffective government. Whether or not global government could ever be a real or desirable possibility, it has never been an actuality, and so war between nations has always been with us. Warfare within nations, civil war or class war, is not so constant. Reasonably effective government is not impossible.

When dealing with people whom you don’t know, the difficulty that you have no basis to trust them as individuals can be resolved to the extent that you can trust that the government will work to maintain the interaction within the frameworks it has established. You have effective recourse if the other party fails to live up to their end of the bargain.

Trust in government can falter for many reasons. The government can simply be too weak or remote to be effective. But a government that fails to be impartial is also not trustworthy, at least for those who get the short end of the stick. If individuals in some group within society cannot rely on the government to resolve their disputes with others outside that group, then the conditions are ripe for some kind of civil war.

Is rich versus poor really a class distinction? Certainly we do regularly estimate each other’s wealth status and view them from that perspective. But I suspect that class divisions are not quite the same as wealth divisions, though of course they are highly correlated. The distinction that really matters for class warfare is that of political power. If there are groups that can steer the government so that the frameworks it establishes are biased in their own favor, that bias undermines the trustworthiness of government and creates the conditions for class warfare.

The fundamental problem of politics is that imbalances in power tend to amplify themselves. Good government may be possible, but it is not stable. It requires constant work to identify and correct bias. The best way to correct bias is to remove the mechanisms that create the bias. A much less satisfactory method is to introduce additional mechanisms with the opposite bias, in hopes of producing a total result that is unbiased.

Taxation is a nice example where these questions of bias are at play. To what extent is wealth inequality a result of bias in government? To what extent do the rich create governmental structures that reinforce their own wealth?

In the vision of the proper role of government that I am sketching here, the government’s role is not to create the world we want. It is our responsibility as members of society to create that world. The government’s proper role is indirect. It is to create a framework for the interaction of members of society, to enable them more effectively to create that world together. Of course some people will want one kind of world and others will want a different sort of world. The proper role of government is not to resolve those differences, but simply to create a common framework where issues of diversity and conformity can be negotiated between individuals.

From this perspective, it would be entirely inappropriate to put higher taxes on wealthy individuals for the purpose of reducing wealth inequality. But look at how government functions preferentially to enhance the wealth of the wealthy! For example, a huge fraction of the federal budget is devoted to international relations. These relations are managed to nurture and protect business relationships such as foreign investments, trade, etc. Certainly we all benefit from the trade in coffee, bananas, etc., but such international business benefits the wealthy preferentially to a very great degree. Given that government benefits the wealthy much more than the poor, it makes perfect sense that the wealthy should provide a similarly greater degree of financial support for those government operations. Or, for another example, when foolish bankers and foolish home buyers entered into foolish lending relationships, it does seem quite unfair to bail out the lenders and hand the resulting tax bill to the borrowers.

Perhaps there is some natural logic to the rich getting richer. What is of fundamental importance is that the government not be biased toward enhancing the power of any such powerful group, or even be perceived as having such a bias. Such bias is the fuel that feeds class warfare. We are reaching a point where there are concentrations of wealth and power that can and do dominate the government and steer the development of laws and regulations to amplify their own advantages. To recognize this bias and to work to correct it is not to engage in class warfare, but to fight against it.