Wednesday, July 21, 2010

Architectures

SISD Uniprocesssor (single instruction stream, single data stream)
SIMD (Vector)
single instruction, multipe data
MIMD (multiprocessors) - our space
multiple instruction, multiple data

Understand the nature of the machines you're running on.

Shared Bus, distributed
Memory contention, communication contention, communication latency...networks of shared memory clusters and processors

Mutual exclusion --

Basic spin lock (spin lock) (critical section) (resets lock upon exit), introduce sequential bottleneck, Amdahl's law, bad thing... queuing up to get to critical section & perform piece of code. Lock suffers from contention. These are distinct phenomena.

Seq bottleneck --> no parallelism

Boolean value, test and set, swap true with current value, return value tells if prior value was true or false, can reset just by writing false.
TAS aka getAndSet

Test and Test and Set locks
Lurking stage / wait until lock "looks" free
spin while read returns true (lock taken)
Pouncing state (left thumb top dot pain intensity threshold)

Mystery #2, Mystery - both, TAS & TTAS do the same thing (in our model) except TTAS perform much better

Shared Bus - broadcast medium - one broadcaster at a time - processors and memory all "snoop"

Snoopy protocol.**

Processor prosser have small caches, 1 or 2 cycles, address & state information

new multicore chips have intermediate shared caches (L1 close to prosser very fast) L2 cache shared and a it slower, memory-much slower

Cache Coherence -

Write back cache -

prosser signal others "I've just changed data" using bus protocol.

Invalid, Valid, Dirty - raw seething

acquire write permission - notify everyone else you're changing it

only get data from memory if haven't found it in someone else's cache

minimize traffic on bus
request lock get as fast as can not slow everyone else down

measuring quiescence time
tom andersen
x = time of ops that don't use the bus. y = time of ops that cause intensive bus traffic

tom andersen

backoff lock - just put some backoff lock
Smart locks - machine learning

false sharing
padding
jonathan - makes smart locks (MIT phd student)

CLH lock

NUMA machine, memory distributed among processors, accessing data locally is really quick, if I have to go to a memory location that's far away, that's expensive.

MCS - Mellor Crummy and Scott, Explicit Pointers
A record, a bit, also a pointer.
allocate a node.
perform same kind of swap in CLH lock.
I know who the guy before me is.
I'm not gonna spin, I wanna spin on my record, that's the one that's local.

Purple spin on purple green spin on verde.

yo cambio la pointer, igoto his knowd and pawnt it to moi

red guy has inst'd his nowd, red gay spins, eventually purple will change dat to valz.

herez how mcs werks

qnode phalse tayle atauhmik

queue

phyx phointer

compare and swap to check if the tail pointer (node) is still pointing to me

if tail is still pointing to me, then nobody in queue, comparison operator, reaching consensus to agree that there is no tail

couldn't do this with reads and writes

compare and swap (MCS Queue lock)

other guy couldn't have been there, can't get in, has gotta notify me

then i spin

why do I spin now? Because I validated that if I failed the CAS, then if...

when he does I'm gonna let him go, I'm gonna release him.




Saturday, June 26, 2010

The Story So Far...

In 1982, a variety of things happened, among them everything that happened in 1982 is ancient history, our story begins in the mid nineties, where computers and infrastructure started to become cheap enough that you could reach people anywhere in the world and tell them things or keep track of things in some kind of non-local location where even if your house and town burned down you could still keep a continuous record of what was going on in your life in so many places that it would be inconvenient to hunt down and destroy everything that it is which you came to represent...

So today, I notice that I am in touch and aware of the conscious volitions, from moment to moment, expressed by leaders all around the world. I am able to wonder to notice the covariance between my actions and the actions of people like Barack Obama, because I am able to monitor the online presence of people like this, and I am able to send signals to the internet which make their way into the websites of his agents. Let me give you an example of how this happens.

I found a twisty little maze of passages in the mind of some guy who explored caves and laid down some of the infrastructure that gave rise to the system that I was interacting with. Inside these passages I found a method for permuting strings of characters into discrete configurations specifying certain destinations or outcomes in terms of information exchange, I could remember paths to access certain memories by short semantic referents, and it became unnecessary for me to store all of the information that I require in order to operate locally.

In order for the system I used to work, I had to carefully define who I trust. Right now, I putatively trust too many sources, I rely upon inputs from too many different nodes in the network, several of which generate unreliable data streams from which I abstract information. This is because I have not consolidated all of the reliable information into one isolated container, and structured a method for sending queries to and from that container, the integrity of which I can rely upon. So I am required to keep my critical barrier operating in order to control the salient variables in my environment which I track. If you shut off your critical barrier, you may get bombarded with a variety of information which interjects itself into your processing cue and causes you to notice an increase in the amount of uncertainty that you experience with regard to a particular phenomenon that you are tracking, you can lose track of the ball, or you can even lose track of the goal associated with the ball or the general scheme of intentionality that you were operating on prior to shutting off your critical barrier. Another way of saying this is that you may notice several coincidences or bell inequalities, the tracking of which may allow you to gain insight into how to cause similar coincidences or bell inequalities.

This place, Kaliningrad, which I am introducing you to, is a fictional place. It could just as easily correspond to some real place, like a Russian town called Kaliningrad, but instead of thinking about some literal town, I prefer that we define Kaliningrad as a metasyntactic variable, or container for a place which could be organized into any arbitrary number of discrete states, which may share common elements but are seperate and distinct from each other. For example, the Kaliningrad which I am presently holding in my mind as the current instance of Kaliningrad at the current iteration of Kaliningrad in the evolution process that tracks all past and all future Kaliningrads (so yes, I guess you can isolate a particular dimension, and set up intervals of that dimension which can be measured in increments implying the existence of a directionality, that is, numbers going forwards and backwards to infinity or negative infinity along a real or imagined axis...), this Kaliningrad is a mirror image of an abstract island on the fictional planet Auberean. I in fact have no way of identifying whether Auberean is a fictional planet, but it is convenient for me to consider it only the representation of a planet and not an actual planet, because if I claim that it is an actual planet then it puts an evidentiary burden on me to specify its location and allow you to make some observation to verify my claim, and the truth is that for the current purpose the ostensible motive which I have granted myself for selecting this Island is to illustrate a principle related to a general feature of Kaliningrad, which is that Kaliningrad has information flowing in and out of it.

A close examination of this island, Kaliningrad, reveals that Microsoft collaborated with Turbine to distribute the original templates which gave rise to the experience of the users of Kaliningrad. Inclusive within this distribution was technology for the creation of portals, which allowed the user, through volitional acts, to transport itself through the island with minimal time delays, there is perhaps, generally, a 3-4 second average delay between entering a portal and emerging at its dropoff point, but this form of travel is much quicker than walking, taking vehicles, flying, or any other known form of transportation. This idea was appropriated by various other world-constructors, such as the designers of Rubi-Ka, who created "the grid" which itself was a twisty little maze of passages functioning as a sort of metaphysical subway system allowing transport of agents and fixers across the landscape by hacking into wormholes in the fabric of virtual representations of spacetime.

There is a variety of equipment that was accessible to me while I visited Rubi-Ka and Kaliningrad, which my avatar on this planet, I don't like Earth, the nomenclature is so monosyllabic, so I am going to call this planet Ispar. Although I use the term Ispar to literally designate the planet we call Earth, I tend to think of Ispar also as a metasyntactic variable, and its usage to characterize Earth as kind of a colloquialism. On a more fundamental level, I regard Ispar as an intermediate world to which an Earthling's consciousness can be connected through little twisty mazes of passages (or portals), and I think that there is an event which occurs during which the consciousness of a humanoid from Ispar is usurped by an earthling, who programs the Isparian to respond to its inclinations and impulses through a brain machine interface connected to the earthling's computer, but since the actions of the Earthling become causally attributed to the Isparian it is convenient for me to regard the home planet of the Isparian as Earth, since it is Earth where the Isparian's volitions originate. The heruistic I use in order to minimize the kolomorgorov complexity or number of characters in the program I run to communicate my referential intention to you or number of transactions required to execute the volition associated with the referential intention I experience which drives me to share information with you...it is convenient for Ispar to be a metasyntactic variable which alternately represents an unknown undisclosed location from which avatars emerge, and also the home planet where the volitions of these avatars originate.

It occurs to me that I do not know that each Isparian's volitions originate on earth, I do not know if astronauts in outer space are portalling into Kaliningrad using Isparian avatars or other avatars. I do not know to what degree the Earthling control of the Isparians is mitigated by Virindi control of Isparian impulses, or what influences the old ones, who in turn influence their agents, who in turn exert influences upon the island of Kaliningrad. I know some of their true names, and by true names, I do not mean that when I speak these names that I am able to call each of the salient individuals to whom I am referring, I merely mean that these are the names that were given for these individuals in the worlds I occupied which were the templates from which the island of Kaliningrad was appropriated. Some of those names were, Aerfalle, Rytheran, Kemeroi...and Kemeroi was itself a vernacular word, the same entity which was called Kemeroi by the masses was identified as nameless by Aerfalle, my understanding is that a preacher named Ilservian Palacost came into contact with this entity, one of the old ones, in a desert, and that somewhere in this desert he experienced a type of transfiguration which led to a path of ascension which enabled the effects of his rage and unfocused aggression to echo around the world, inspiring terror and slaying the hopes of many of those adversaries he encountered.

I have incompletely visualized a scenario in which six individuals--Uweden, Rajael, Kerenth, Adja, Maila, and Asheron--collaborated to imprison this transfigured Ilservian Palacost inside of a crystal. This was due to some ethnic conflict which resulted in a battle at a town, Daralet, on the isle of Kaliningrad, where several children were recruited in order to form an army that laid waste to the Yalani invaders responsible for denying Ilservian's son Avoren access to food or water, which became the probable impetus for Ilservian's unfocused aggression; this act of recognition which he experienced, in retroactively assessing the stream of contingencies which culminated in the loss of his offspring, gave rise to a set of emotions which, in connection with some escalation of commitment trust bond formed with the one Aerfalle refers to as nameless, gave rise to behaviors which the Isparian councils felt necessary to contain and ultimately banish from Auberean.

The problem that emerged is that Ilservian, through his interaction with this Old one, had become organized into some form which allowed for his periodic incarnation in various avatars distributed across points in the landscape, and his consciousness also moved through his armies, he was as much an idea and legend as he was a discrete individual, and keeping track of and containing his influence proved to be a task associated in some respects with physical containment of the expression of his extended phenotype, but also with media campaigns and generally, mobilizing protective barriers of psychic defenses for individuals that might become susceptible to his call...he is responsible for slaying Asheron's father, so Asheron has been one of the primary individuals responsible for supplying my networks with information about how to manage the domain of events associated with bombardment of messaging units from sources connected to the Palacost family and the tragedies which have been visited upon some of their spirits.

It has been a long time since I visited Kaliningrad, however, it is not difficult to keep track of what is going on over there by visiting the various portals that link to and provide information about the activities in this island. Originally, I understand there was only one bridge to Kaliningrad, but soon thereafter there were seven, and ultimately there were hidden bridges, easily accessible bridges, networks of caves containing a twisting little maze of underground passages leading to portals leading to points on the surface of Kaliningrad which could be accessed by anyone who knows how to navigate through them, which can be dangerous and difficult, for example, because some of these caves are inhabited by giant insectoids with sharp, swift, large pincers, antennae, acid sprays, eyes, legs, carapaces, I don't know if they have ears, or if they notice sound waves...I ought to know, having spent so much time in their lairs, but I do not recall any particular occasions where they noticed the sounds I was making. What it seems they do is patrol some area of their cave until you enter into their field of vision, then they attempt to run directly towards you, and so many of my encounters with these creatures consisted of circumventing obstacles, running through passages, jumping to from cliffs to ledges, running in circles around fixed barriers, attempting to out-think these creatures, attempting to negotiate myself into places where these creatures would not be able to reach me, where they would smash into walls and try to do work by applying force to an unmovable barrier between myself and themselves, or to be spatially located in some position higher than they could jump to reach me. From these vantage points I would drain their life, stamina, and mana or conjure shock waves or other means for injuring them beyond a threshold at which they would no longer be capable of threatening me during my exploration of their caves.

As I understand it, these Olthois enslaved the Isparians who originally portalled to Kaliningrad, but their queen was assasinated by an Alluvian female who became a consort of Asheron.