1

Paleocybernetics: Technology and the prehistoric imaginary in American art of the 1960s and 1970s

Larisa Dryansky

Toward the end of Sapiens (2011), Yuval Noah Harari's recent popular history of the human species from the first appearance of Homo sapiens up to the present, the author evokes the possible "return of the Neanderthals" as a consequence of the reconstruction of the fossil hominid's genome. 1 This mention occurs in a chapter devoted to the conceivable demise of Homo sapiens in which Harari details how humankind at the turn of the twenty-first century is about to transcend its biological limits through different means of intelligent design, which herald the possibility of a godlike species emerging in our place. 2 In this context, the evocation of the resurgence of the Neanderthals not only serves to illustrate scientific ingenuity but, more importantly perhaps, underscores the book's central tenet, which is that, as it reaches its most advanced technological stage, humanity's fate is to become quite literally a prehistoric fossil.

The mix of pessimism and awe contained in this account of evolution perfectly captures the mood of the day with respect to technology, and the publication's success is easy to understand. But, unbeknownst perhaps to its author, Sapiens also rehearses a topos that already has its own archaeology. 3 In the 1960s and 1970s, as the electronic revolution was just beginning, futuristic I would like to express my gratitude to Amy Plumb Oppenheim, Steina and Woody Vasulka, Dave Hanson, Maggie Creshkoff, Chelsea Spengemann, and Jean-Marie Dallet. My thanks as well to the anonymous peer reviewer of this essay whose comments were very helpful, and to the editors of this issue, Maria Stavrinaki and Stefanos Geroulanos. 1 Y. N. Harari, Sapiens: A Brief History of Humankind (London, 2011), 451-53. 2 Harari, Sapiens, 445-64. 3 I am using the term "topos" here in the media archaeological sense defined by Erkki Huhtamo. E. Huhtamo, "Dismantling the Fairy Engine: Media Archaeology as Topos Study," in Media Archaeology: Approaches, Applications and Implications, ed. E. Huhtamo and J. Parikka (Berkeley, 2011), 27-47. visions were often coupled with the prehistoric imaginary. Indeed, while in the aftermath of the two world wars the horrors of modern technological warfare fostered a "regressive analogy between prehistory and modernity," 4 with the advent of the "information society" a concurrent paradigm took hold, grounded in the idea that mankind was on the brink of an evolutionary leap as momentous as that which saw the emergence of Homo sapiens. As today, this pre/posthistoric vision generated both anxiety and excitement. Yet, by throwing a bridge across the abyss of time between the dawning electronic age and the dawn of mankind, this approach also suggests that the binaries of progress and regress, of techno-euphoria and technophobia are not sufficient frameworks for engaging with the temporal complexity of technology. Excavating this moment-our own immediate prehistory-encourages us to read the present moment of technological upheaval against the grain and complicate the dialectic between human and technological evolution.

As paleontology reminds us, the onset of tool-making marks the real beginnings of humankind and technics are thus integral to the definition of humanity. 5 It is true that the rise of the computer age constituted a crucial turning point in this respect. The art theorist Jack Burnham, a key advocate for the alliance of art and technology in this period, summarized the problem well when he distinguished between homo faber and what he termed homo arbiter formae: "As a culture producer, man has traditionally claimed the title Homo Faber: man the maker (of tools and images). With continued advances in the industrial revolution, he assumes a new and more critical function. As Homo Arbiter Formae his prime role becomes that of man the 4 M. Stavrinaki, "'Enfant né sans mère, mère morte sans enfant': Les historiens de l'art face à la préhistoire," Les Cahiers du Musée National d'Art Moderne, no. 126 (Winter 2013-14): 10. 5 See K. P. Oakley, Man the Tool-Maker (London, 1949), and A. Leroi-Gourhan, Le geste et la parole, vol. 1, Technique et langage (Paris, 1964). maker of esthetic decisions." [START_REF] Burnham | The House That Jack Built: Jack Burnham's Concept of 'Software' as a Metaphor for Art[END_REF] Burnham embraced this change, but the 1960s were also a time when automation caused great concern about the loss of the most basic manual skills. For artists, in particular, invoking prehistory could serve as an appeal for a lost authenticity, "a need to see art become useful again, beginning with a recognition of the insights it can provide into life and nature-their human significance in an age of dehumanized technology." [START_REF] Lippard | Overlay: Contemporary Art and the Art of Prehistory[END_REF] Yet references to prehistoric times may also be viewed, perhaps more fruitfully, as an invitation to reconnect with the primordial nature of technics and, rather than positing technology as an alien force, make it natural again, so to speak.

In How We Became Posthuman (1998), her essential study of the human-machine interface in the age of information, N. Katherine Hayles details how, starting in the postwar period, the assumption that information is disembodied has fed the fantasies about the advent of a posthuman species superseding humanity. Against the materiality/information divide, Hayles focuses on the history of science and on examples drawn from literature to show the continued dynamic tensions between human embodiment and the idea of a disembodied technology. [START_REF] Hayles | How We Became Posthuman: Virtual Bodies in Cybernetics, Literature, and Informatics[END_REF] Hayles does not refer to the "prehistoric idea," [START_REF] Stavrinaki | Editorial[END_REF] nor does she address other areas of culture outside of literature. But, as just mentioned, in approximately the same period in which she begins her study, artists interested in the intersections between art and science and in the artistic potentialities of new media engaged with these same issues. The phenomenon was not limited to the United States, but, because of the country's technological advance and because artists' access to new technologies was earlier and more widespread there, the American art scene offers an exemplary case to investigate this topic. In this context, I argue, the prehistoric imaginary was one of the privileged sites for engaging with the issue of disembodiment. If, on the one hand, the coupling of futurism with the prehistoric imaginary promoted a "cool," abstract vision of prehistory, on the other, artists also drew on the idea that the sensibility of the prehistoric world was predominantly tactile to bring out by comparison the haptic dimension of modern technology.

This was most explicitly the case in the discourse surrounding the then nascent medium of video art, the first full-fledged form of electronic visual art. Video, despite its name, is not primarily an optical medium. It is a signaletic technology in which sound is just as likely to occur as images. 10 In this respect, video could be apprehended as breaking with the ocularcentrism associated with the art of modernity, whether it be the perspectival tradition that emerged during the Renaissance, or, its apparent anti-model, the disembodied opticality of high modernism as theorized by Clement Greenberg in the postwar period. In addition, the temporality of video had the unprecedented appeal of immediacy. Contrary to film, video is not constituted by a series of still images, but by a continuous stream of electronic impulses. Its time in this regard is that of a ceaselessly ongoing present, which in effect appears to dissolve the linear succession of historical time.

According to Pamela Lee, this aspect of video renders it one example among many of "chronophobia," which in her account of time in the art of the 1960s is a defining characteristic of the period. Although Lee does not address the theme of prehistory directly, it works as a good illustration of her thesis that artists' "increasingly fraught confrontation with technology" in a world dramatically reshaped by technological acceleration translated into "an almost obsessional uneasiness with time and its measure" and a sense of "noncontemporaneity, of not being with the time."11 However, if the chronological disjunctions attached to the prehistoric imaginary could function as temporal evasions, they also could work as a reminder of the multidimensionality of time in a moment obsessed with the new. In approximately the same period studied by Lee, the paleoanthropologist André Leroi-Gourhan summarized this question well, stating that "[t]echnology, a word with a specific meaning in modern industrial terminology, spreads progressively from the television set to the chipped flint tool." 12 With this deliberately counterchronological description of the connection between the Stone Age and the electronic age, Leroi-Gourhan invites in effect an illuminating reversal of perspective: rather than looking at modernity through an archaic lens, with all the technophobic biases this view can entail, discovering prehistory itself as already "technological."

Coding prehistory: The cybernetic model

The equation between modern technology and prehistory is not recent, in fact, but has its roots in the time of the industrial revolution. To the Victorians, railroads, for instance, were evocative of dinosaurs, a comparison facilitated by the prehistoric relics unearthed in the process of building the rail tracks. [START_REF] Freeman | Victorians and the Prehistoric: Tracks to a Lost World[END_REF] This analogy was perhaps best captured by Lewis Mumford, who, borrowing a term coined by Patrick Geddes, 14 defined the nineteenth century's industrial revolution as a "Paleotechnic" phase sustained by an energy source dating from the carboniferous period: coal. [START_REF] Mumford | [END_REF] Drawing on the stereotype of prehistory as an era dominated by brute force, Mumford also used this comparison to condemn the industrial age, decreeing that the Paleotechnic age generated a new form of barbarism. 16 With the 1960s, however, a new revolution was underway. Heavy industry was losing ground to informatics, "carbon" giving way to "silicon" [START_REF] Deleuze | Foucault[END_REF] -a shift vividly reflected by the film critic Gene Youngblood in 1970:

We're in transition from the Industrial Age to the Cybernetic Age, characterized by many as the post-Industrial Age. But I've found the term Paleocybernetic valuable as a conceptual tool with which to grasp the significance of our present environment combining the primitive potential associated with Paleolithic and the transcendental integrities of "practical utopianism" associated with Cybernetic. So I call it the Paleocybernetic Age: an image of a hairy, buckskinned, barefooted atomic physicist with a brain full of mescaline and logarithms, working out the heuristics of computergenerated holograms or krypton laser interferometry. It's the dawn of man: for the first time in history we'll soon be free enough to discover who we are. [START_REF] Youngblood | Expanded Cinema[END_REF] It is likely that Youngblood conceived the neologism "Paleocybernetic" on the model of Mumford's "Paleotechnic." Like Mumford, Youngblood plays on the clichéd perception of prehistory as a time peopled by primitive, still animal-like human beings. But unlike Mumford's apocalyptic vision, Youngblood's picture is utopian. Placed at the beginning of Youngblood's influential book Expanded Cinema (1970), it sets the tone for his visionary survey of recent artistic uses of technological images, from light shows and experimental film to video art, computer generated imagery, and holographic cinema. The prehistoric imaginary occupied a central position in the development of expanded cinema, a point I will return to. For now, it is necessary to turn to the field of cybernetics, which, according to Youngblood, displaced industry while opening the possibility of a radical new beginning for humankind.

The term "cybernetics" was coined by the mathematician Norbert Wiener to designate the theory of communication and control in living organisms and machines, which evolved out of the work he and his fellow scientists, Arturo Rosenblueth and Julian Bigelow, conducted for the American military during the Second World War on anti-aircraft artillery. Their aim was to improve the efficiency of the weapons by finding a method for the control apparatus of the gun to predict the future position of its target. 19 They found the solution to this problem in the function of "feedback": "the property of being able to adjust future conduct by past performance." 20 The notion of feedback initially applied to mechanisms, but Wiener extended it to nervous systems. In 1950, Wiener first published his popular introduction to cybernetics, The Human Use of Human Beings: Cybernetics and Society. The concept of cybernetics soon was adopted, often indiscriminately, by a wide variety of disciplines beyond mathematics and information theory, and the name itself became a sort of umbrella term for the most advanced technology. In particular, the way in which Wiener's investigations put on a par living organisms and machines led to futuristic speculations on the emergence of "cyborgs," technologically ameliorated versions of the human species. 21 Wiener's own vision was, however, much bleaker. As mentioned, cybernetics was born during World War II, and in Wiener's writings it retains the impress of this apocalyptic time, which concluded with the atomic bomb. The notion of entropy was central to Wiener's theory: the idea that all systems tend to deteriorate and lapse into a state of chaos and sameness. The purpose of feedback is to fight entropy. Yet, in the end, nothing can prevent the fact that "[i]n a very real sense we are shipwrecked passengers on a doomed planet." 22 The specter of heat death looms large over Wiener's world, and if there is a prehistoric element about cybernetics as he defined it, then it stems from a conception of prehistory akin to H. G. Wells's portrait of the ultimate return of the universe to original chaos in The Time Machine (1895) and not to the techno-futuristic fantasy described by Youngblood.

To better understand the conflation of cybernetics and the Paleolithic, it is instructive to see how the image of prehistory itself was modified during this period. The traditional conception of prehistory as a brutish era did not subside in any way, as exemplified by movies, the radio, and the printed word. "Cool" media, on the other hand, are characteristic both of the age of information and communication introduced by electricity and of preliterate worlds.

Sacrificing definition for speed, they require intense participation from the receiver who needs to fill in the missing data. The television and telephone are for McLuhan prime instances of "cold" media, as is the aboriginal medium of speech itself or, in a different way, the prehistoric stone axes still found among "Australian natives" in modern times. [START_REF] Mcluhan | Understanding Media: The Extensions of Man[END_REF] Interestingly, in the field of prehistoric studies itself comparable ideas were being developed at the same time. 26 In 1963 and 1964 the British astronomer Gerald Hawkins published two groundbreaking articles on Stonehenge in which, backing up his study with the aid of a computer, he attempted to demonstrate that the Neolithic site was a solar and lunar observatory whose functioning was based on highly complex and accurate calculations. [START_REF] Hawkins | Stonehenge Decoded[END_REF] A few years later, engineer and amateur archaeologist Alexander Thom published Megalithic Sites in Britain, in which he summarized his controversial theory regarding the existence of a prehistoric science of geometry and astronomy. [START_REF] Thom | Megalithic Sites in Britain[END_REF] Similarly, at the end of the sixties the historians of science Giorgio de Santillana and Hertha von Dechend argued in favor of a megalithic origin of science. [START_REF] De Santillana | Hamlet's Mill: An Essay on Myth and the Frame of Time[END_REF] This revision of prehistory as a scientifically sophisticated period had a lasting impact, as witnessed by Overlay (1983), Lucy Lippard's survey of the prehistoric drive in contemporary art. Casting a retrospective glance at the art scene of the sixties and seventies, Lippard established a connection between the supposed "international preliterate code language of numbers, motions, and measures" of the Neolithic and minimalism's use of mathematical series. 30 Writing during the heyday of minimal art, Robert Smithson chose for his part to go even further back in time, stating of the "new monuments" of minimalist sculpture that they brought to mind the "Ice Age." 31 Repudiating accounts of art's evolution based on a biological template, Kubler posited a pattern akin to the recursive causality of feedback. According to this scheme, "[art] history moved not forward but backward, and then forward again," 34 an idea vividly captured by Smithson when he stated: "The future is always going backwards. Our future tends to be prehistoric." 35 Although Lee does not linger on this theme, the prehistoric imaginary was an important component of Smithson's "chronophobic" use of cybernetics. It is probably not beside the point to recall that in the 1960s the Mesoamerican cultures that were Kubler's objects of study were viewed as prehistoric, a perception to which Smithson himself subscribed. 36 But Smithson also drew inspiration from the recent speculations on the existence of prehistoric forms of coding, as revealed by his essay "The Artist as Site-Seer: Or, a Dintorphic Essay" (1966-67), which was unpublished in the artist's lifetime but contains many clues for understanding his art. 37 In it, Smithson refers to Hawkins's theory of Stonehenge as a computer, which he opposes to traditional interpretations of the site as a "primitive Druid Temple"; Hawkins's technological Stonehenge becomes in Smithson's text an archetype of "environmental coding," that is, a conception of the environment as essentially artificial and abstract rather than natural. 38 Prehistory appears as an elastic notion in this essay, which also includes references to Kubler, the pyramids of Egypt, and the "megaliths" that adorn the postapocalyptic landscape of J. G. Ballard's science-fiction short story, Terminal Beach (1964). Stretching to encompass Alexander Graham Bell's various technical inventions along with structuralist theory and direct mentions of 34 Lee, Chronophobia, 245. 35 R. Smithson, "Fragments of an Interview with P. A. [Patsy] Norvell," in Flam, Robert Smithson,194. 36 Roberts, Mirror-Travels, 109-10. 37 R. Smithson, "The Artist as Site-Seer; Or, a Dintorphic Essay" [1966-67], in Flam, Robert Smithson, 340-45. 38 Smithson, "The Artist as Site-Seer," 340. cybernation, Smithson's technologically inflected vision of prehistory comes across in the end less as a futuristic projection and more as an eclectic version of Wilhelm Worringer's inorganic abstraction updated for the computer age. [START_REF]On Worringer's antinaturalist view of "primeval art[END_REF] Smithson's interest in prehistoric "coding" was in effect short-lived. As he explained in 1971 in answer to a question on the Nazca lines, the ancient Peruvian geoglyphs that were a source of inspiration for several of the Earthworks artists: "The Nazca lines have meaning only because they were photographed from airplanes, at least for our eyes conditioned by the twentieth century. All we can do is use our orders and systems to investigate them, and they generally turn out to be wrong-like 'Stonehenge Decoded.' Stonehenge doesn't strike me as a Neolithic computer. What is interesting is how we fail to understand such remote things." [START_REF] Smithson | …The Earth, Subject to Cataclysms, Is a Cruel Master[END_REF] Smithson's definition of prehistory as unknowable recalls Georges Bataille's earlier conception of the unintelligibility of prehistoric art. [START_REF] Bataille | Lascaux ou la naissance de l'art[END_REF] As for whatever futurism might have been contained in Smithson's attraction to cybernetics, it appears in the end to have been overshadowed by his fascination with entropy. 42 Indeed, as Smithson's work evolved, so, in a kind of reversion to the prehistoric projections of the machine age, [START_REF]On Smithson's "paleotechnic" vision of prehistory, see L. Dryansky[END_REF] did his references to prehistory become more explicitly a part of his "desublimation of the technological sublime." [START_REF] Jones | Machine in the Studio: Constructing the Postwar American Artist[END_REF] If Smithson ultimately dissociated his conception of prehistory from notions of coding, Dennis Oppenheim absorbed these ideas in a way that was not guided by an antinaturalist abstraction like the work of his colleague, but by the question of embodiment. Oppenheim's work constitutes an original and instructive example of how artists brought together prehistory and the cybernetic age. At first sight, however-and excepting the fact that he used media such as photography, film, and video to document his pieces-there seems to be nothing remotely technological about either the content or the appearance of Oppenheim's work from this period.

On the contrary, the artist's oeuvre has often been associated with ancient ritualistic practices, starting with Burnham who in 1973 famously compared Oppenheim's working methods "to the traditional techniques used by the shaman in so-called primitive societies." 45 But the link between Burnham and Oppenheim also invites another reading of the artist's approach. If Burnham viewed Oppenheim as a "shaman," he also cast him as one of the leading figures of the new post-object art of the information age. 46 As mentioned earlier, Burnham was one of the main proponents in America of a futuristic fusion of art and technology. In his first book, Beyond Modern Sculpture (1968), he depicted the evolution of the ties between sculpture and technology as a process of increasing dematerialization leading in contemporary times to a "systems aesthetics" modeled on systems theory and cybernetics, and, from then on, in the near future, to the ultimate demise of sculpture itself. Like Youngblood, he also believed that the twentieth century was "the beginning of a critical transition for the whole human species" and that the leap to a "post-human species" was imminent. 47 Progressively, however, Burnham's language switched from utopian to frankly mystical. This turn may in fact have been suggested to him by the precedent of prehistory. In Beyond Sculpture, he reached back into prehistorical times to account for the emergence of robot and cyborg art, relating the apparition of these new forms of automata to the prehistoric association of art, magic, and science depicted by Arnold Hauser in The Social History of Art (1951). 48 In Burnham's later writings this interest in magic led, however, to a departure from scientificity.

Systems and structures became contemporary incarnations of the Kabbalah. 49 This is the phase to which belongs his view of Oppenheim as a shaman. But if Burnham strove to spiritualize technology, and in particular ideas derived from cybernetics, Oppenheim, on the contrary, experimented in his "prehistoric" work with how to embody these same notions.

Oppenheim's interest in information theory and cybernetics has been overlooked despite several traces of these themes in his work from the 1960s and '70s. The most explicit examples are two performances involving the artist's children: Feedback (1971) and A Feed-Back Situation (1971). In Feedback, Oppenheim traces with his finger on his teenage daughter's shirtless back a series of letters. The daughter articulates the letters individually without necessarily making out the sequence. The letters spell out profane words related to sex, which only the father can understand. 50 In A Feed-Back Situation (fig. 1), Oppenheim and his young son, Erik, stand shirtless next to each other with their backs turned to a Super 8 camera. Each tries to reproduce on the other's back the tracings which he feels at the same time being drawn on his own body. The process of exchange and the intertwined arms enact a kind of primeval, physical feedback system while the lines drawn on the backs circle in ways vaguely reminiscent 48 Burnham, Beyond Modern Sculpture, 312. 49 M. Ragain, "Introduction," in J. Burnham, Dissolve into Comprehension: Writings and Interviews 1964-2004, ed. M. Ragain (Cambridge, MA, 2015), xxi. 50 My thanks to Amy Plumb Oppenheim for clarifying the structure and the content of this piece. of feedback loops. With their punning titles, these performances might be understood as parodies of the period's infatuation with cybernetics. 51 But, if provocation is not absent from the feedback pieces, 52 they also have an intensity that indicates a deeper content. Contrary to the idea of cybernetics as an abstract, hyper-technological theory, Oppenheim here invests it with an almost raw materiality, which simultaneously gestures in the direction of the beginnings of art, the words traced by the artist on his daughter's back evoking rough, finger-drawn prehistoric pictures, while the lines traced blindly by father and son in response to each other's touch bring to mind the entangled prehistoric digital tracings on cave walls, which, according to Sigfried Giedion, were also executed in a state of semi-blindness due to the obscurity of the caverns. 53 The connection between feedback processes and tactility is in effect a recurrent motif in Oppenheim's work from this period. A good illustration is Identity Stretch (1970-75), which again involves the question of the relation, or feedback, between parent and offspring (fig. 2).

For this piece, Oppenheim had his thumbprint and that of Erik enlarged thousands of times and transferred in asphalt onto a field in Upstate New York. Like several pieces of land art, the work evokes Neolithic geoglyphs. More importantly, the giant thumbprints monumentalize that most ancient procedure of image-making, the very "dawn of images," 54 which is the impress. Accordingly, Rosalind Krauss cited Identity-Stretch as an emblem of the "indexicality" that for 51 It is also highly likely that Oppenheim was inspired by the anthropologist Gregory Bateson's use of the notion of cybernetics, and particularly feedback, as applied to behavioral science. The artist's archive contains a clipping of an article by Bateson translated into French and illustrated with works by Oppenheim, including Feedback. I have not been able to trace the source of this document so far. My warmest thanks again to Amy Plumb Oppenheim for exhuming this archive and bringing it to my attention. 52 her was the defining feature of 1970s art. [START_REF] Krauss | Notes on the Index: Seventies Art in America[END_REF] Krauss, it is true, downplayed the prehistoric sources of such work. [START_REF] Krauss | Sculpture in the Expanded Field[END_REF] Yet in her description of how the index "ced[es] the language of art back to the imposition of things," it is hard not to hear echoes of a primordial conception of art. 57 At the same time, such an approach overlooks the technical considerations that entered into the making of Identity-Stretch. It is important to specify that Oppenheim did not transfer the thumbprints directly, but "made them on elastic material, pulled to maximum, then photographed." 58 While impresses may belong to an archaic mode of image-making descended to us from prehistory, there is, as Georges Didi-Huberman reminds us, nothing rudimentary about them. [START_REF] Didi-Huberman | La ressemblance par contact: Archéologie, anachronisme et modernité de l'empreinte[END_REF] Making an impress is a technique, [START_REF]La ressemblance par contact[END_REF] a fact which Oppenheim in his way demonstrates with his manipulation of the thumbprints. But even more significant is how his stretching of the thumbprints brings out the looping motif formed by the papillary ridges, which, once more, evokes a feedback pattern. In the same period in which he conceived Identity-Stretch, Oppenheim also created a piece called Identity Transfer in which he figured the transfer of identity from one family generation to the next by having his eldest child touch his thumb with her own, then he in turn touch his father's thumb, and, finally, the latter apply his thumb to the ground as if to leave its impress on the earth's surface (fig. 3). Commenting on this work and on the content of the "transfer" enacted, Oppenheim, who was probably thinking of the discovery of the genetic code, explained: "You're transferring coded information." [START_REF] Sharp | Interview with Dennis Oppenheim[END_REF] As in A Feed-Back ideas were immensely inspiring for artists engaged in exploring the creative potential of the new communication technologies. In particular, the project of replacing a tradition of ocularcentrism with a predominantly tactile model found resonance in the synesthetic environments of "expanded cinema," a loosely defined category grouping film installations, video art, light shows, and artistic experiments with pioneering image technologies.

One of the most complete illustrations of this constellation between expanded cinema, tactility, and prehistory is Stan VanDerBeek's Movie-Drome, a metal dome structure erected by the experimental filmmaker on an artists' commune in Stony Point, just north of New York City (fig. 4). The Movie-Drome was intended as a prototype for an unrealized global communication system in which several domes would be positioned throughout the world, each linked to orbiting satellites that would store and transmit images between various sites, 65 providing an artistic interpretation of the McLuhanite idea of the "global village." Inside the building, VanDerBeek, who is believed to have coined the term "Expanded Cinema," 66 organized multimedia presentations combining slide and film projections from various sources: outtakes from his own experimental films, art historical and anthropological slides, found footage and stock imagery, bits of newsreels, abstract images made by the artist in pressed-glass sides, and so on. 67 The dome was inaugurated in 1966 during the New York Film Festival with a presentation significantly entitled Feedback, situating it squarely within the fascination for cybernetics characteristic of the times. However, despite the visionary nature of this project, the Movie-Drome also constituted, as Gloria Sutton indicates, a "decidedly low-tech context." 68 Sutton makes a keen distinction between, on the one hand, the immersive multimedia experience created by the Movie-Drome, which relied on simple equipment and did not attempt to deceive the viewer, and, on the other, the sophisticated illusionism of the "widescreen vernacular" and other new media forms that began to develop in this period, heralding current virtual reality technologies. 69 In effect, not only was the technical implementation of the Movie-Drome relatively unsophisticated, but, I want to argue, it generated a sensory environment designed to procure a prehistoric experience akin to that described by McLuhan.

For the first viewers of Feedback, the initially most striking aspect of the event was perhaps quite simply the fact of seeing images projected on the curved surface of a dome wall. propagandistic, motives of the Eameses. 71 The difference is apparent in the way each installed their images in space. In the environments that the Eameses designed, the image remains contained by a frame. Despite an impression of profusion, the couple's multiscreen technique organizes the images on strictly separate surfaces. Paradoxically, this tidy division creates an effect that is "intentionally cohesive, rather than disjunctive," the images "reinforcing one another to communicate a single, unmistakable message of limitless abundance and prosperity." 72 By contrast, in the Movie-Drome the images overlapped without merging, recalling the superimposition of heterogeneous figures in cave paintings, which has so long intrigued prehistorians (fig. 5). Floating in space, they appear completely unmoored from the flat and welldefined surface that, according to Greenberg's then very influential views on art, was supposed to have been the support of images since humankind outgrew its prehistoric condition: "The Paleolithic painter or engraver could disregard the norm of the frame and treat the surface in a literally sculptural way only because he made images rather than pictures, and worked on a support-a rock wall, a bone, a horn, or a stone-whose limits and surface were arbitrarily given by nature. But the making of pictures means, among other things, the deliberate creating or choosing of a flat surface, and the deliberate circumscribing and limiting of it." 73 With the spherical Movie-Drome, VanDerBeek broke with the "norm of the frame," thus returning the "picture" to its primeval condition as "image." Indeed, the endless and chaotic stream of projections produced a sensory overload, which was meant to exceed the capacities of visual representation itself. 74 The filmmaker in this respect seems to have been following quite closely McLuhan's notion of "auditory" or "acoustic space" as opposed to visual space. McLuhan developed this idea largely in dialogue with Carpenter, who himself first encountered it in his research on "Eskimos." In the article "Acoustic Space," which McLuhan and Carpenter jointly published in their journal Explorations, they described this space in terms that apply very well to the Movie-Drome's environment and its transformative experience: 75 "a sphere without fixed boundaries […] It is not pictorial space, boxed in, but dynamic, always in flux, creating its own dimensions moment by moment. It has no fixed boundaries; it is indifferent to background. The eye focuses, pinpoints, abstracts, locating each object in physical space, against a background; the ear, however, favors sound from any direction." 76 Alexander Nagel has demonstrated convincingly how this space corresponded for McLuhan to a "return to the medieval integration of the senses after centuries of subjection to the visual systems of ordering." 77 But just as important, it seems, were the connections McLuhan established between the electric age's sensorium and the world of "pre-literate man." Thus, in an interesting case of a circular exchange of ideas, McLuhan in 74 Sutton, The Experience Machine, 96. 75 Sutton mentions that VanDerBeek owned a copy of Explorations's eighth issue, and that he was an avid reader of McLuhan's writings: Sutton, The Experience Machine, 54 and 57. defining what he viewed as the indifference of non-literate men to visual values referred to Giedion's study of the conception of space in prehistoric art, which, in turn, was indebted to Carpenter's work. 78 Indeed, Giedion, like Carpenter and McLuhan, insisted on the "audible" rather than "optical" nature of prehistoric space, meaning that prehistoric space, like sound, was not structured around a fixed point of view and could spread in all directions simultaneously: 79 "Primeval art has no background…This is inherent in the prehistoric conception of space: all linear directions have equal right and likewise all surfaces, whether they be regular or irregular.

They can be tilted at any angle with the horizontal throughout the entire 360 degree range. To the eye of primeval man, animals that to us appear to be standing on their heads do not appear inverted to him because they exist, as it were, in space free from the forces of gravity." 80 As a point of fact, sound was a crucial component of the Movie-Drome presentations. The audience that attended Feedback remarked on the way the sound reverberated throughout the room and praised the outstanding quality of the acoustics. 81 Even more noteworthy was the way in which VanDerBeek played with the spatialization of image and sound to disorient the viewer: "the multidirectional movement of the projectors (affixed to a central turntable or wheeled carts) caused the aluminum walls to appear to pulsate while the changing tone and pitch of the soundtracks created acoustic reverberations around the space making it impossible to correlate specific sounds with their filmic sources." 82 To intensify the experience, VanDerBeek instructed 78 McLuhan, The Gutenberg Galaxy, 65-66. On Giedion and Carpenter, see S. Papapetros, "Modern Architecture and Prehistory: Retracing The Eternal Present (Sigfried Giedion and André Leroi-Gourhan)," in "Wet/Dry," special issue, Res: Anthropology and Aesthetics 63-64 (2013): 183-84. 79 Giedion, The Eternal Present, 526. 80 S. Giedion, "Space Conception in Prehistoric Art," in Explorations in Communication, 86-87. This essay directly follows Carpenter and McLuhan's "Acoustic Space" in this volume. 81 Sutton, The Experience Machine, 31. 82 Sutton, The Experience Machine, 95. sophisticated ways. However, the tactile quality of his video art did not diminish (quite the contrary), nor, despite his often repeated assertion that video was a new form of painting, did he revert to a pictorial type of representation. As David Zerbib remarks, Paik's handling of electronic matter to produce distorted images may be fruitfully compared with the "alteration drive," which according to Bataille lies at the origin of representation. [START_REF] Zerbib | Paik, Heidegger and the Chelsea Girl; Or, Electronic Ecstasy Unveiled[END_REF] Following this theory, the will to alter the support, to inscribe a trace in matter, is prior to any attempt at mimetic representation.

For the art historian René Berger, who produced some of the earliest criticism on video art, and who was also well-versed in the writings of McLuhan, "the sophisticated tool that is electronics is paradoxically very close to the first bifaces of prehistory…Chronology is dissolved, traces turn to tracings, tracings in turn become trajectories, leading back symbolically to the hand impresses left by cavemen on the walls of their caverns." [START_REF] Berger | L'art vidéo: Défis et paradoxes[END_REF] This return to a prehistoric condition of the image must not be confused with a new case of primitivism in modern art. As Paik's example demonstrates, the pioneers of video art were on the contrary fascinated with the novelty of electronic technology and its specific properties. Rather, with the "Paleocybernetic" medium of video they were able to address anew the relation between technology and the senses and to rediscover the technical environment as a space for experimentation, "an open field of symbolization, as it was in Paleolithic times when men invented writing." 89

Videory: Video's "prehistoric" temporality

With video, then, it seemed as if it were possible for humanity to retrace its footsteps back to the moments just prior to the beginnings of history. More radically, video appeared to make the very notion of history obsolete. As Paik declared: "The word 'history' came into being, because our events were told and written down thereafter. Now history is being recorded in image or video. Therefore from now on there is no more 'History,' but only 'Imagery' or 'Videory.'" 90 What Paik was alluding to was not just the switch from a literate to a post-literate society. Rather, his statement pointed to the different time consciousness introduced by video, one which was perceived as completely novel, but which also seemed to connect modern man again to prehistory, as suggested by one of Paik's most important video installations, Moon Is the Oldest TV (1965-92) (fig. 6).

The piece was first created in 1965 for Paik's inaugural solo exhibition in New York at the Bonino Gallery, before going through different versions. The basic principles of the installation, however, remained the same. It is composed of several TV monitors (from eleven to seventeen) placed on pedestals, which are aligned in a row. The screens feature circles and circle segments evoking the phases of the moon. These images are not played from a tape, but are created by modifying the internal workings of the TV sets, moving the picture tube scanner back and fixing a magnet at the neck of the tube. As Edith Decker-Phillips notes in her thorough technical description of the work, the bluish-white light emanating from the picture tube adds to the uncanny impression that one is seeing an actual broadcast of the real moon. 91 At the same time, the stillness of the forms appearing on the screens contradicts the idea of "real time" that is 90 N. J. Paik, "Binghamton Letter, Jan. supposed to be the defining feature of TV and video. The impression of timelessness, which is clearly designated in the work's title, is also underscored by the installation. The monitors sitting atop high pedestals take on a solemn, even monumental appearance, not unlike that of the minimalist "monuments" that for Smithson evoked the Ice Age. 92 Indeed, it would not be farfetched to compare them to megaliths. The astronomical theme of the piece encourages as well a comparison with Stonehenge. 93 "There is a myth that TV is an 'instant' medium," explained Paik in the early 1970s, "where as [sic] a metal sculpture is a 'permanent' medium." 94 Although this might appear in contradiction with the image of Paik as an iconoclastic Fluxus performer, he was much preoccupied with issues of preservation and permanence. Because it facilitated storage and retrieval of information, Paik viewed video as the contemporary medium best expressing the "Cult of Eternity" at the root of art. 95 Technical evolution has of course proved him wrong. But Paik's notion of video as connected to eternity touches also on something more fundamental: the idea that the medium's temporal essence is of a different nature from that of time as it is commonly understood. Instead of the immediate time of "real presence," it may in fact be better defined as the time of the "continual" or "eternal present," which according to Giedion was a characteristic of prehistoric art. By this Giedion did not mean that prehistoric art denied the flow of time, but more complexly that it displayed "the perpetual interflow of today, yesterday, and 92 Smithson, "Entropy." 93 Toward the end of his life, Paik directly referenced prehistory in an installation entitled From Neander Valley to Silicon Valley (1996). It presents an anthropomorphic robot composed of vintage and recent TV sets, fur, antlers, stone, and wood. 94 N. J. Paik, "Software Projects (in collaboration with Jud Yalkut) [1972-73]," in Nam June Paik: Videa 'n' Videology, n.p. 95 Paik, "Software Projects." tomorrow" whose multidimensionality precedes and exceeds the measure of clocks. 96

  19 N. Wiener, Cybernetics: or Control and Communication in the Animal and the Machine [1948] (Cambridge, MA, 1961), 5. 20 N. Wiener, The Human Use of Human Beings: Cybernetics and Society (Boston, 1950), 33.

  Youngblood's own text. But, alongside it, a cooler, more technological projection took hold. I use the term "cool" here deliberately to reference Marshall McLuhan (Youngblood's other major inspiration along with Buckminster Fuller). The media theorist's writings were indeed crucial in popularizing the notion of the age of information as a new prehistoric era. McLuhan himself drew on Wiener, deriving from the scientist the idea of the preeminent role played by communication technologies in shaping culture as well as the analogy between technological and 21 The term "cyborg" first appeared in 1960 in an article by Manfred E. Clynes and Nathan S. Kline. M. E. Clynes and N. S. Kline, "Cyborgs and Space," Astronautics, September 1960: 26-27 and 74-76. 22 Wiener, The Human Use of Human Beings, 40. physiological operations. But McLuhan discarded Wiener's mathematical theory of information, bending the scientific framework of cybernetics to his interests in literature and art. 23 Significantly, as Fred Turner reminds us, McLuhan discovered cybernetics at the same time that he was engaging with ethnography and so-called primitive art through his collaboration with his colleague at the University of Toronto, the anthropologist Edmund Carpenter. 24 Their exchanges resulted in a joint seminar on the new media of communication and in the interdisciplinary journal Explorations: Studies in Culture and Communication (1953-59). Echoes of McLuhan's dual interest in tribalism and communication run through his work, particularly in the parallels between the preliterate man of prehistory and the post-historic man of the electronic age.According to McLuhan, the speed of electric means of communication, abolishing both temporal and spatial distances, collapsed the rational and mechanistic world that arose with the invention of Gutenberg's printing press and reached its apogee in the industrial age. In its place a new era was emerging, one characterized by a "retribalization" of the world linking humanity across the globe and by a resurgence, through the most up-to-date audiovisual technology, of a culture of orality characteristic of both extinct prehistoric cultures and surviving preliterate societies. In McLuhan's system these cultures are also designated as "cool." The categories of "cool" and "hot" are pillars of McLuhan's media theory. "Hot" media belong to the preceding "age of literacy." High in definition, they leave little for the audience to complete. Such are the23 On Wiener and McLuhan, see D. F. Theall, The Virtual Marshall McLuhan (Montreal, 2001), 30 and 127; F. Turner, From Counterculture to Cyberculture: Stewart Brand, the Whole Earth Network, and the Rise of Digital Utopianism (Chicago, 2006), 52-53; and J. Bonnett, Emergence and Empire: Innis, Complexity, and the Trajectory of History (Montreal, 2013), 329-30n29. According to Nam June Paik, whose work I look at in the following pages, McLuhan's optimism put Wiener's pessimism "inside-out, as Marx put Hegel upside-down." N. J. Paik, "Norbert Wiener and Marshall McLuhan: Communication Revolution," Kyoto Prize lecture, 1998: http://www.kyotoprize.org/en/laureates/nam_june_paik/. 24 Turner, From Counterculture to Cyberculture, 53.

  65 S. VanDerBeek, "'Culture Intercom' and Expanded Cinema: A Proposal and Manifesto," The Tulane Drama Review 11, no. 1 (1966): 38-48. G. Sutton, The Experience Machine: Stan VanDerBeek's Movie-Drome and Expanded Cinema (Cambridge, MA, 2015), 11. My descriptions of the Movie-Drome are indebted to Sutton's excellent study. 66 For the history of this term, see Sutton, The Experience Machine, 199n5. 67 Sutton, The Experience Machine, 31.

  Projections on spherical surfaces were not, in fact, a totally novel experience. As Andrew Uroskie recounts, early reviews of VanDerBeek's expanded cinema tended to associate it with the circular cinema of Charles and Ray Eames. In 1959 the couple famously presented their film Glimpses of the USA on multiple screens inside a Fuller geodesic dome at the 1959 World's Fair in Moscow, a technical feat repeated at the 1964 World's Fair in New York with the projection of Think inside the IBM ovoid building. 70 Such comparisons, however, were based on a misconception, VanDerBeek's intentions differing completely from the didactic, and even 68 Sutton, The Experience Machine, 97. 69 Sutton, The Experience Machine, 96-97. 70 On these installations, see B. Colomina, "Enclosed by Images: The Eameses' Multimedia Architecture," Grey Room, no. 2 (Winter 2001): 5-29. Fred Turner has coined the term "surround" to refer to such circular environments: F. Turner, The Democratic Surround: Multimedia and American Liberalism from World War II to the Psychedelic Sixties (Chicago, 2013).

  71 A. V. Uroskie, Between the Black Box and the White Cube: Expanded Cinema and Postwar Art (Chicago, 2014), 166-67. 72 Uroskie, Between the Black Box and the White Cube, 167. 73 C. Greenberg, "Modernist Painting" [1960-61], in The Collected Essays and Criticism, vol. 4, Modernism with a Vengeance, 1957-1969, ed. J. O'Brian (Chicago, 1993), 92.

  76 E. Carpenter and M. McLuhan, "Acoustic Space," in Explorations in Communication: An Anthology, ed. E. Carpenter and M. McLuhan (Boston, 1960), 67. This volume collects articles culled from the journal Explorations. Branden Joseph points out that McLuhan, in his later publication, The Medium Is the Massage (1967), illustrates the concept of "auditory space" with a photograph of a multimedia performance by Andy Warhol's Exploding Plastic Inevitable. The bombardment of the senses provoked by the EPI indeed exemplifies the multidirectional nature of acoustic space. But, as Joseph also indicates, their aggressivity stands in stark distinction to the utopia of tribal unity. B. W. Joseph, "'My Mind Split Open': Andy Warhol's Exploding Plastic Inevitable," Grey Room, no. 8 (Summer 2002): 88-91. 77 A. Nagel, Medieval Modern: Art out of Time (London, 2012), 156.

  photography and film. As indicated, VanDerBeek's original idea was to use satellite transmission

  Paik furnished another illustration of this idea with the installation TV Clock (1963-81), a piece made prior to Moon Is the Oldest TV. It likewise consists of television monitors presented on high plinths with modified screens showing fixed abstract patterns that evoke the hands of a clock without actually imitating them. 97 In this manner Paik ironically presents the supersession of human clock time by the eternal time of electronic technology. All the same, Paik's critique of history stopped short of anti-humanism. A decade earlier, as the electronic revolution was just beginning, McLuhan announced with a strange kind of enthusiasm that "[h]istory has been abolished by our new media. If prehistoric man is simply preliterate man living in a timeless world of seasonal recurrence, may not post-historic man find himself in a similar situation? May not the upshot of our technology be the awakening from the historically conditioned nightmare of the past into a timeless present? Historic man may turn out to have been literate man. An episode." 98 Against such a perspective, Paik expressed a strong desire to humanize technology, 99 and even let slip his hatred of technology. 100 From this point of 96 Giedion, "Space Conception in Prehistoric Art," 85-86. 97 Decker-Phillips, Paik Video, 68-69. 98 M. McLuhan, "Culture without Literacy," Explorations: Studies in Culture and Communication, no. 1 (1953): 119. 99 Zerbib, "Paik and the Humanization of Technology," 6-20. Zerbib relates Paik's concern for this question to the anti-technocratic approaches of both Martin Heidegger and the Frankfurt School. Another possible link, which has yet to be explored, is with the radically anti-modernist theory of Hans Sedlmayr, the controversial art historian whose seminar Paik attended as a student when he first came to Germany in the mid-1950s. In his book Verlust der Mitte (1948), Sedlmayr, a leading figure of the Viennese School, but also a former member of the Nazi party, devotes a section to the "dehumanization" wrought by technology in modern times. H. Sedlmayr, Art in Crisis: The Lost Center, trans. B. Battershaw (London, 2017), 238-40. Paik's attendance of Sedlmayr's seminar is mentioned in T. Kellein, "Die Welt der Kunst der Welt: Nam June Paik als Philosoph," in Nam June Paik: Video Time, Video Space, ed. T. Stooss and T. Kellein, exh. cat. (Basel, 1991), 30. 100 See e.g. N. J. Paik, "Nam June Paik California/New York/Boston Video Synthesizer Plus," 1970, in Nam June Paik: Videa 'n' Videology, n.p.

  Smithson's art and writings during this moment are themselves emblematic of a "cool" sensibility sustained by a dual fascination with prehistory and futuristic technology. Eugenie Tsai and Jennifer Roberts have well documented the connections in Smithson's work between a crystalline form of primitivism and science fiction. 32 As Pamela Lee has admirably demonstrated, this interest in futurism also extended beyond fiction to the science of cybernetics, an interest which Lee relates directly to Smithson's engagement with issues of temporality. Lee thus excavates the essential contribution of Wiener's notions of feedback and entropy to Smithson's artistic dismantling of historical time. This connection was enriched by Smithson's conflation of cybernetic temporality with the recursive model of time put forth by the Mesoamericanist George Kubler in The Shape of Time: Remarks on the History of Things (1962), a book that is itself shot through with references to electric circuitry and signaling. 33 30 Lippard, Overlay, 82. For Lippard's discussion of Hawkins, Thom, and de Santillana and von Dechend, see 80-84 and 115-16. 31 R. Smithson, "Entropy and the New Monuments" [1966], in Robert Smithson: The Collected Writings, ed. J. Flam (Berkeley, 1996), 11. 32 E. Tsai, "The Sci-Fi Connection: The I. G., J. G. Ballard, and Robert Smithson," in Modern Dreams: The Rise and Fall and Rise of Pop, exh. cat. (Cambridge, MA, 1987), 70-75. Roberts, Mirror-Travels, 109. See also T. A. Zaniello, "'Our Future Tends to Be Prehistoric': Science Fiction and Robert Smithson," Arts Magazine 52, no. 9 (1978): 114. 33 Lee, Chronophobia, 219-56. On Smithson and cybernetics, see also M. Maffei, "Robert Smithson et la cybernétique: Langage, technologie et abstraction" (PhD diss., Université Paris 8 Vincennes Saint-Denis, 2016).

  See S. Delpeux, "Paternités de Dennis Oppenheim," Les Cahiers du Musée National d'Art Moderne, no. 99 (Spring 2007): 53-61.

53

Giedion, The Eternal Present, 54-55.

54

A. Leroi-Gourhan, Le geste et la parole, vol. 2, La mémoire et les rythmes (Paris, 1964), 212-16.

  8, 1972," in Nam June Paik: Videa 'n' Videology 1959-1973, exh. cat. (Syracuse, NY, 1974), n.p. 91 Decker-Phillips, Paik Video, 71.

I. Blom, The Autobiography of Video: The Life and Times of a Memory Technology (Berlin, 2016), 20.

P. M. Lee, Chronophobia: On Time in the Art of the 1960s (Cambridge, MA, 2004), xx, xii, 223.

A. Leroi-Gourhan, Évolution et techniques, vol. 1, L'Homme et la matière [1943] (Paris, 1971), 316.

J. Burnham, "Artists as Shaman"[1973], in Burnham, Great Western Salt Works, 140.

J. Burnham, "Real Time Systems," Artforum 8, no. 1 (1969): 49-55.

J. Burnham, Beyond Modern Sculpture: The Effects of Science and Technology on the Sculpture of This Century (New York, 1987), 371.

Situation and in Identity Stretch, Oppenheim was engaging here with a nexus of ideas derived from cybernetics, which was then radically affecting the concept of "nature" by aligning organic functions with information processing. Thus, alongside both posthuman fantasies and Smithson's profoundly ambivalent position toward technology, Oppenheim invites a different approach in which technology is given a corporeal density. By combining references to technology and to the biological operations of generation, he points in effect to the prehistoric emergence of technics, when, to borrow from Leroi-Gourhan, tools were first "exuded" like a natural organ from the brain and the body. 62 From picture back to image: Prehistory, tactility, and expanded cinema Of all the bodily senses it is primarily with touch that Oppenheim connects feedback. Indeed, tactility is a key notion for understanding how in this period the technology of the electronic age could be related to a primeval sense of organic wholeness. This aspect was best theorized by McLuhan, for whom the immediacy and ubiquity of electronic communication technologies not only recreated the "tribal" world on a global scale, but, perhaps more importantly, introduced a profound shift in the structuring of the sensory apparatus of modern Western humankind. According to this theory, whereas vision had been the dominating sense since the Renaissance, the electric age reestablished the tactile "interplay of the senses" characteristic of "pre-literate man." 63 Although McLuhan insisted as well on the disruptive aspects of such changes-he also qualified the electric age as the "Age of Anxiety" 64 -these 62 Leroi-Gourhan, Le geste et la parole, 151-52. 63 M. McLuhan, The Gutenberg Galaxy: The Making of Typographic Man (London, 1962), 65. 64 McLuhan, Understanding Media, 5. view, Paik's engagement with video is perhaps less instructive than that of his fellow pioneer of electronic art, Woody Vasulka, whose work stemmed from a fascination with the fact that "the machine is basically indifferent to our needs and wishes." 101 One of Vasulka's early videos stages this indifference with an illuminating reference to prehistory. In a passage from this tape-entitled, significantly, Evolution (1971)-Vasulka manipulates the image of a chart of human evolution so as to give the impression of accelerating the progression of figures from hominid to Homo sapiens while simultaneously figuring an irresistible movement of regression by having the images slide horizontally in reverse (fig. 7). Vasulka created the sequence's antievolutionary and paradoxical play with time by using an effect called "horizontal drift," which he had recently discovered by accident. This feature, which is specific to the video image, makes it possible to slide video frames horizontally across the screen, an effect that Vasulka also contrasted with the vertical scrolling of film frames in the projector. 102 In the case of Evolution, the horizontal orientation of the image designates a break both with anthropomorphic verticality and with the evolutionary pattern of history, humankind being returned here to its prehistoric state. As the tape progresses, in effect, human figures fade away. They are replaced first by TV sets and then by abstract, electronically generated forms. The final images show these shapes sliding back and forth in a manner reminiscent of the earlier procession of hominids, thus completing the process of replacement of a human-centered world by a machinic one.

In her remarkable study of early video as a memory technology, Ina Blom rightly insists on the differences between video time and human time: "For all the early emphasis on real-time procedures, video times were not necessarily calibrated to our sense of time, the normal human perception of motion. In fact, they often did not even attempt to address human attention, but appeared to turn inward, privileging a series of properly machinic timescapes." 103 Evolution presents such a machinic timescape. In a sense, the tape may be understood as a rejoinder to the period's speculations on the assumption of Homo sapiens to a higher stage of humanity. But Vasulka's approach more subtly undermines both techno-utopian and technophobic positions, reminding us that in order to fully take on the phenomenon of technology it is necessary to begin by questioning our human-centered biases. It is this decentering that, ultimately, provides the prehistoric imaginary with its enduring actuality. 103 Blom, The Autobiography of Video, 101.


Jan Carlson
email: jan.carlson@mdh.se

Jukka Mäki-Turja

Mikael Nolin

Event-Pattern Triggered Real-Time Tasks *

We present the concept of pattern-triggered tasks which are released when a particular pattern of events occur. A formal event algebra is used to de ne complex triggering conditions for these tasks, and the detection of triggering conditions is performed within the system by code generated automatically from these de nitions. The implementation of the algebra has many desirable features for resource constrained real-time systems, including bounded and low execution time and memory consumption. Furthermore, we present novel schedulability analysis for our pattern-triggered tasks that leverage on existing analysis for xed-priority and dynamic-priority scheduling policies.

Introduction

In this paper we present the concept of patterntriggered tasks. Pattern-triggered tasks are released for execution when a, potentially complex, pattern of events occur. The events and the triggering conditions are formally speci ed by an event algebra that allow complex combinations of events to be expressed [START_REF] Carlson | An Event Detection Algebra for Reactive Systems[END_REF]. To guarantee bounded response-times and make our systems amenable for scheduling analysis, the individual events that build up these event patterns are assumed to be sporadic with a known minimum interarrival time.

Our event algebra has attractive properties making it suitable for engineering of resource constrained real-time systems. First and foremost, the algebra provides simple and intuitive operators (e.g., conjunction, disjunction and sequence). Furthermore, the code for pattern detection can be automatically generated from the event expressions, and exhibits necessary qualities in order to be used in resource constrained real-time systems: (i) it is resource ef cient, and bounded, with regards to memory footprint as well as processing time; (ii) worst case execution time (WCET) can easily be analysed by automated tools since the code only contains simple programming constructs.

Pattern-triggered tasks can be realised without explicit Example As a running example throughout the paper, we consider a system where the external events are a button, a pressure alarm and a temperature alarm, and where the desired behaviour includes performing a particular response when both alarms have occurred, unless the button is pressed in between.

The rest of the paper is organised as follows: Section 2 surveys related work, and Section 3 de nes the task model and describes how pattern-triggered tasks are realised. Section 4 presents the event algebra used to de ne event patterns, including formal semantics and important properties. The generation of detection code is described in Section 5, and in Section 6 we present schedulability analysis for task sets including pattern-triggered tasks, before concluding the paper in Section 7.

Related Work

The concept of pattern-triggered tasks is quite different from the concept of event-streams that are used to model chains of tasks by, e.g., Chakraborty et al. [START_REF] Chakraborty | A General Framework for Analysing System Properties in Platform-Based Embedded System Designs[END_REF] and in SymTA/S [START_REF] Henia | System Level Performance Analysis -the SymTA/S Approach[END_REF]. In short, they consider a scenario where tasks are triggered by external events that can have complex occurrence patterns, while in our approach the external events are simple and the detection of signi cant event patterns is performed within the system. Common to the two approaches is that information about event patterns is exploited in the schedulability analysis to achieve more accurate results. Timed automata has been proposed as a modelling language for complex triggering patterns [START_REF] Amnell | TIMES: a tool for schedulability analysis and code generation of real-time systems[END_REF]. However, for practically oriented engineers it is often a daunting task to specify system behaviour using timed automata. Furthermore, the computational complexity of analysing such speci cations with respect to schedulability can be overwhelming. In particular, constructs that require that multiple patterns are detected concurrently, such as conjunction or non-occurrence of a complex pattern, typically result in very large automata compared to the size of the automata detecting the constituent parts [START_REF] Motakis | Formal semantics for composite temporal events in active database rules[END_REF].

More directly related to our approach, Mok et al. [START_REF] Mok | Early detection of timing constraint violation at runtime[END_REF] present a framework based on real time logic (RTL), which is a rst order logic with a dedicated predicate encoding event occurrences. The framework has, for example, been used in the context of network management [START_REF] Liu | Composite events for network event correlation[END_REF] and in an electronic brokerage application [START_REF] Mok | Specifying timing constraints and composite events: An application in the design of electronic brokerages[END_REF]. It has also been suggested as the basis for composite event specication in active databases [START_REF] Liu | A uni ed approach for specifying timing constraints and composite events in active real-time database systems[END_REF]. Bounded detection algorithms are presented, but the memory bound depends on the time constants used in the pattern de nitions and on the minimum interarrival time of events [START_REF] Mok | Early detection of timing constraint violation at runtime[END_REF].

The operators of our algebra are in uenced by work in the area of active databases [START_REF] Chakravarthy | Snoop: An expressive event speci cation language for active databases[END_REF][START_REF] Gatziu | Events in an active objectoriented database system[END_REF][START_REF] Gehani | COMPOSE: A system for composite speci cation and detection[END_REF]. The use of interval semantics to avoid unintended semantics for some operation combinations was proposed by Galton and Augusto [START_REF] Galton | Two approaches to event de nition[END_REF]. Our restriction policy, used to achieve resource bounds, resembles the concept of event contexts found in e.g., Snoop [START_REF] Chakravarthy | Snoop: An expressive event speci cation language for active databases[END_REF] and Solicitor [START_REF] Mellin | Resource-Predictable and Ef cient Monitoring of Events[END_REF], but is different in that we apply it once to the whole expression rather than to each operator individually.

Event Pattern Triggered Tasks

A straightforward way to construct an embedded system that reacts to a particular event pattern is to include a task which performs pattern detection implicitly within the code and then performs the desired reaction if the pattern is detected.

The drawback of this straightforward approach is that the execution time of the task varies a lot, since the response code is only executed when the full pattern is detected. If pattern occurrences are rare compared to the occurrences of individual events, analysis techniques based on a single WCET value will be very pessimistic, meaning that the system must be signi cantly underutilised in order to statically guarantee timeliness of all tasks.

Alternatively, pattern detection and response can be split into two tasks. This allows tighter WCET information, but does not solve the utilisation problem. With no information about the nature of the pattern, it must be assumed that the response task is executed as often as the detection task.

We propose a task model where triggering patterns are de ned explicitly rather than implicitly in the task code. This separation of concerns facilitates both design and analysis. Complex event patterns can be speci ed on a high level of abstraction, independently from the rest of the application in which they are used, and the rest of the system is free from detection related code and information about partially completed patterns.

With a formal syntax and semantics, the detection code can be automatically generated from pattern speci cations, relieving the programmer of this error prone task. Also, the patterns are available for analysis, in particular to establish how frequently the pattern can occur in the worst case, which allows a more ef cient use of resources compared to assuming that the complicated event occurs as often as its constituent simple events.

Example task model and assumptions

For the sake of presentation, we adopt a relatively simple task model including both periodic tasks and tasks that are triggered by particular patterns of sporadic events. The system is fully preemptive and scheduled according to either EDF or FPS. Ordinary sporadic tasks are treated as a special case of pattern-triggered tasks where the pattern consists of just a single event. Extending the task model to include precedence constraints, blocking caused by shared resources, etc., should be straightforward.

A task, τ i , is characterised by the following parameters:

• Worst case execution time (C i ) The longest time it could take to execute the code of the task, assuming that it is not interrupted.

• Relative deadline (D i ) The time, relative to activation, when the task must be nished.

Each task also has one of the following parameters, depending on if it is periodic or pattern-triggered:

• Period (T i ) The time between two consecutive activations of a periodic task.

• Event expression (E i ) A speci cation of the situation under which a pattern-triggered task should be activated.

Note that for pattern-triggered tasks, C i refers to the execution time of the user provided response code. The worst case execution time associated with the generated detection code of an event expression E i is denoted by wcet(E i ).

Under FPS, the following parameter also applies:

• Priority (P i ) The static priority of the task.

Task instances that have the same priority are assumed to be served in the same order as they are released. Ties are broken arbitrarily. Example For the running example, we let the system consist of three tasks, two of which are periodic (τ 1 and τ 3 ). The third task, τ 2 , is triggered by the event pattern both alarms (P and T) occur without the button B being pressed in between. In the event algebra, elaborated in Section 4, this situation is speci ed by the event expression (P+T)-B. The parameters of this example task set are: In a situation when several events occur before the rst has been processed, multiple instances of a patterntriggered task will be active at the same time. Under FPS, they have the same priority, but the rst-come-rstserved assumption guarantees that the events are processed in the correct order. For EDF, this is ensured by the fact that the absolute deadlines of the instances follow the order in which the events arrived.

Task P i C i T i D i E i
The reason for including the conceptually different activities of event detection and response in the same task is related to the fact that the original deadline of a patterntriggered task is relative to the pattern occurrence, not the time at which the pattern is detected [START_REF] Berndtsson | Issues in active real-time databases[END_REF]. If detection and response were handled by separate tasks, the response task could not be statically assigned a deadline relative to its activation, which is prescribed by the traditional task model.

The Event Algebra

This section presents the event algebra used to specify triggering patterns, focusing on aspects that are most relevant to the scope of this paper. For an in-depth treatment, including examples motivating the use of interval semantics, comparisons with alternative approaches, and formal proofs of properties, complexity and correctness, see [START_REF] Carlson | Event Pattern Detection for Embedded Systems[END_REF].

The particular characteristics of this event algebra is the combination of satisfying a number of intuitive algebraic laws while at the same time permitting any event expression to be correctly detected with bounded memory.

Syntax

We denote by P the set of external events that the system can react to. In the algebra, they are primitive event expressions, representing the simple pattern of a single event occurring. For more complex patterns, composite event expressions can be built using the operators of the algebra.

De nition 1 If A ∈ P, then A is an event expression. If A and B are event expressions, and if t is a time constant, then A∨B, A+B, A;B, A-B and A t are event expressions.

Informally, a disjunction A ∨ B represents that either of A and B occurs. A conjunction means that both events have occurred, in any order and possibly at different times, and is denoted A+B. A sequence A;B is an occurrence of A followed by an occurrence of B. The negation, denoted A-B, occurs when there is an occurrence of A during which there is no occurrence of B. This description of negation makes little sense when A is primitive, since primitive occurrences are instantaneous. A more typical usage of the negation operator is (A;B) -C, representing that there should be no occurrence of C between the occurrences of A and B. Finally, there is a temporal restriction A t which occurs when there is an occurrence of A shorter than t time units. As with negation, the temporal restriction is typically applied to sequences or conjunctions, restricting the time between the constituent occurrences.

Example

For the example system, we have P = {B, P, T} and the triggering pattern is speci ed by the event expression (P + T) -B. For a more complex example, consider the pattern the button is pressed twice within two seconds, and none of the alarms occurs in between which can be de ned by the event expression (B;B) 2 sec -(P∨T).

Semantics

We represent a single event occurrence by its start-and end time. Although primitive events are assumed to be instantaneous, occurrences of composite events must be represented by intervals in order to achieve some of the desired algebraic properties [START_REF] Carlson | Event Pattern Detection for Embedded Systems[END_REF].

Formally, the interval of an event occurrence a is captured by the functions start(a) and end(a), where end(a) denote the time of occurrence, and the full interval from start(a) to end(a) represents the smallest interval containing all primitive occurrences that caused a.

The operator ⊕ is used to construct occurrences of composite event expressions from occurrences of the constituents.

E.g., each occurrence of A;B will be constructed from one occurrence of A and one occurrence of The following de nition formalises the algebra semantics:

De nition 2 For A ∈ P, [[A]] is the set of all occurrences of A. For composite event expressions, the semantics is de ned as follows:

[[A∨B]] = [[A]] ∪ [[B]] [[A+B]] = {a ⊕ b | a ∈ [[A]] ∧ b ∈ [[B]]} [[A;B]] = {a ⊕ b | a ∈ [[A]] ∧ b ∈ [[B]] ∧ end(a) < start(b)} [[A-B]] = {a | a ∈ [[A]] ∧ ¬∃ b∈[[B]] (start(a) ≤ start(b)∧ end(b) ≤ end(a))} [[A t ]] = {a | a ∈ [[A]] ∧ end(a) -start(a) ≤ t}
This de nition results in an algebra with simple semantics and intuitive algebraic properties. However, the memory required to perform the detection is unbounded for some expressions. For example, when detecting A;B each occurrence of A must be remembered forever, since it should be combined with all future occurrences of B.

To deal with resource limitations, we introduce a formal restriction policy that de nes a subset of occurrences that must be detected. The basic idea is to ignore simultaneous occurrences, while at the same time retaining the desired of the semantics.

The restriction policy is de ned as a binary relation res.

Rather than computing the full [[A]

] for a given event expression A, an implementation of the algebra is expected to detect a set of event occurrences S such that res(A, S) holds.

Informally, from the occurrences with the same end time, exactly one with maximal start time must be detected. For the user of the algebra, this means that at any time when there is one or more occurrences of A, one of them will be detected.

De nition 3 For an event expression A and a set S of event occurrences, res(A, S) holds if: Now, the laws can be formulated. For proofs and a more extensive set of laws, see [START_REF] Carlson | Event Pattern Detection for Embedded Systems[END_REF].

1. S ⊆ [[A]] 2. ∀ a∈[[A]] (∃ s∈S (start(a) ≤ start(s) ∧ end(a) = end(s))) 3. ∀ s,s ∈S (end(s) = end(s ) ⇒ s = s )
Laws 1 For arbitrary event expressions A, B and C, and any time constant t, the following laws hold:

A∨A ≡ A A∨B ≡ B ∨A A+B ≡ B +A A t ≡ A if A ∈ P (A t ) t ≡ A min(t,t )

A∨(B ∨C) ≡ (A∨B)∨C

A+(B +C) ≡ (A+B)+C

A;(B;C) ≡ (A;B);C

Laws 2 For arbitrary event expressions A, B and C, and any time constant t, the following laws hold:

(A∨B)+C ≡ (A+C)∨(B +C)

(A∨B);C ≡ (A;C)∨(B;C) A;(B ∨C) ≡ (A;B)∨(A;C) (A-B)-C ≡ A-(B ∨C) (A∨B)-C ≡ (A-C)∨(B -C) (A∨B) t ≡ A t ∨B t (A-B) t ≡ A t -B
These laws identify expressions that are semantically equivalent, but in order to deal with resource limitations, we expect an implementation of the algebra to compute an event stream S such that res(A, S), rather than computing Thus, A ≡ B ensures that for any implementation consistent with the restriction policy, the occurrences detected for A are always a valid result for B as well. Thus, any reasoning based on the algebra semantics and restriction policy, and not on details of a particular detection algorithm, will be equally valid for equivalent expressions.

Implementation

A primary ambition when designing the algebra has been to allow an implementation for which bounds on memory footprint and processing time can be determined statically. This section presents how a concrete online detection algorithm can be generated automatically from an event expression. The detection algorithm has a memory and time complexity of O(m

2 ) where m is the size of the expression.

This is an improved version of the algorithm compared

to what has been previously published [START_REF] Carlson | An Event Detection Algebra for Reactive Systems[END_REF], where bounds on memory and time could only be established for a subset of expressions.

Detection algorithm

Figure 2 presents an algorithm that detects occurrences of a given event expression A. The numbers 1 . . . m are assigned to the subexpressions of A in an arbitrary bottom-up order, and we let A i denote subexpression number i. Consequently, we have A m = A.

The symbol ε is used to represent a non-occurrence, and we de ne start(ε) = end(ε) = -1 to simplify the algorithm. The algorithm is executed every time tick when at least one primitive event occurs, and at the end of execution, the variable a m contains the current occurrence of A, or ε if A did not occur.

The variables used in the algorithm can be divided into three categories. Persistent variables (l, r, Q and t) store information that must be remembered from one time tick to the next in order to detect the event properly. Since each subexpression requires its own persistent variables, they are indexed from 1 to m.

Auxiliary variables (a and S) are used to pass information from a subexpression to its parent node in the expression tree, and are indexed in the same way as the persistent variables. In short, a i is used to store the current instance of subexpression A i , and S i contains possible start times of future occurrences of A i . There are also temporary variables (t, e, e and Q ) that are used locally within a single subexpression in a single tick. These are not indexed, indicating that the content is never used outside that scope.

a 1 := the current occurrence of P a 2 := the current occurrence of T if start(l 3 ) < start(a 1 ) then l

3 := a 1 if start(r 3 ) < start(a 2 ) then r 3 := a 2 if l 3 = ε ∨ r 3 = ε ∨ (a 1 = ε ∧ a 2 = ε) then a 3 := ε else if start(a 2 ) ≤ start(a 1 ) then a 3 := a 1 ⊕ r 3 else a 3 := l 3 ⊕ a 2 a 4 := the current occurrence of B.
if t 5 < start(a 4 ) then t 5 := start(a 4 ) if t 5 < start(a 3 ) then a 5 := a 3 else a 5 := ε

Code generation

The detection algorithm in Figure 2 is formulated for arbitrary expressions, and the main loop selects dynamically which part of the algorithm to execute for each subexpression. When the expression is known at compiletime, the main loop can be unrolled and the top-level conditionals, as well as all indices, can be statically determined. Also, assignments of S i variables can be removed for all subexpressions except those appearing somewhere in the second argument of a sequence operator.

Example The concrete detection algorithm for the event expression in the example system is presented in Figure 3.

Initially, t 5 = -1 and l 3 = r 3 = ε.

Time and memory requirements

The worst part of the algorithm, from a complexity point of view, is the nested foreach constructs in the sequence part. However, this source of complexity can be avoided, without compromising the correctness of the algorithm, if the set variables S i and Q i are represented as ordered structures. This means that the nested foreach constructs can be changed into a single while-loop traversing S i and Q i together. For details, and for the proof of the following theorem, see [START_REF] Carlson | Event Pattern Detection for Embedded Systems[END_REF]. The generated code does not utilise any dynamic memory management, neither by explicit memory allocation, nor by function calls or parameter passing via the runtime stack. Furthermore, the code is characterised by a very simple control ow. For example, there are no subroutine or function calls, and all loops are trivially bounded by the size of some static data structure. Thus, existing techniques and standard tools for execution time analysis, e.g., SWEET [START_REF]Worst case execution times (WCET) project homepage[END_REF], aiT [START_REF]AbsInt company homepage[END_REF] or Bound-T [START_REF]Bound-T homepage[END_REF] should be applicable.

Schedulability Analysis

For the analysis we assume that events are sporadic, i.e., that the minimum interarrival time, denoted mint(A) is known for each A ∈ P.

Example

Before analysing the example task set, we make the following assumptions about minimum interarrival times and worst case detection execution time: With the straightforward approach described initially, where pattern detection is performed implicitly within the task code, this task set would be considered nonschedulable even if the detection overhead is disregarded.

During any time interval of length 4200, 84 instances of τ 1 and 21 instances of τ 3 are released for execution. Furthermore, there can be 60, 21 and 70 occurrences of P, T and B, respectively, potentially triggering 151 instances of τ 2 .

Thus, the total amount of execution that is released during the interval is 84 * 10 + 21 * 30 + 151 * 20 = 4490. Since 4490 units of computation can be released in any interval of length 4200, the task set is clearly non-schedulable.

Introducing pattern-triggered tasks with explicit pattern speci cations, however, permits a more accurate analysis. We will show later that this particular task set is in fact schedulable.

The occurrences of a pattern are in general not sporadic even though the primitive events are. For a simple example, consider two sporadic events P and T. Regardless of the minimum interarrival times of the two events, an occurrence of P can be immediately followed by an occurrence of T, resulting in two occurrences of the pattern P∨T separated by just a single clock tick.

Nevertheless, the frequency at which a pattern occurs can be bounded, but in a more general way than with a single minimum interarrival time.

For example, we can safely state that in any interval of length min(mint(P), mint(T)), there can be at most two occurrences of the pattern P∨T.

This resembles the concept of bursty aperiodic tasks [START_REF] Klein | A Practitioner's Handbook for Real-Time Analysis: Guide to Rate Monotonic Analysis for Real-Time Systems[END_REF] which are triggered by events that can occur arbitrarily close in time, but which are bounded by a constraint specifying that there can be at most n occurrences within any interval of length l.

For patterns, however, it is possible to be more speci c than the two parameters of bursty tasks permit. First, we note that a pattern always occur at the same time as one of the constituent primitive events. In fact, only a subset of the constituent events can directly result in an occurrence of the pattern. For example, A;B always occur at the same time as some B occurrence. The following de nition formalises this idea.

De nition 5 For an event expression A, prim(A) denotes the set of primitive event expressions in A and term(A) denotes the set of terminating primitive events of A, de-ned as follows:

term(A) = {A} if A ∈ P term(A∨B) = term(A) ∪ term(B) term(A+B) = term(A) ∪ term(B) term(A;B) = term(B) term(A-B) = term(A) term(A t ) = term(A)
The central idea in the schedulability analysis of systems with pattern-triggered tasks is that a task responding to occurrences of a pattern requires the same amount of computation resources over time as a particular set of sporadic tasks. A pattern-triggered task is realised by one task which is activated by all events in the pattern, as described in Section 3.2. During the schedulability analysis, however, we view task instances that were activated by one event as instances of a different task than those activated by another event. For example, when τ 2 is activated by P, this is viewed as an instance of a separate task than when activated by T or B. This also allows taking into consideration the information provided by the explicit pattern speci cations, by treating separately those instances that only ever execute the detection code and never the response code.

Formally, from the original task set of periodic and pattern-triggered tasks, we construct a ctive, auxiliary task set which is used for schedulability analysis:

De nition 6 Given a task set Γ, the auxiliary task set Γ aux is the smallest set of tasks such that

• all periodic tasks in Γ are in Γ aux ;

• for each pattern-triggered task τ i ∈ Γ, and each primitive event A ∈ prim(E i ), Γ aux contains a sporadic task τ iA with T iA = mint(A), D iA = D i , P iA = P i and

C iA = wcet(E i ) + C i if A ∈ term(E i ) wcet(E i ) if A ∈ term(E i )
Example The auxiliary task set for the running example, constructed according to De nition 6, is shown below: Since prim((P+T)-B) = {P, T, B}, the pattern triggered task τ 2 results in three sporadic tasks in the auxiliary task set (τ 2P , τ 2T and τ 2B ), with minimum interarrival times given by these primitive events, respectively. From term((P+T)-B) = {P, T} it follows that the WCET of the response code should be included only in τ 2P and τ 2T . Theorem 4 If Γ aux is schedulable then Γ is schedulable.

τ i P i C i T i D i τ 1
Proof: We show that any sequence of Γ task instances can be mirrored by a sequence of Γ aux task instances with the same arrival times, priorities, execution times and deadlines. Since the periodic tasks are the same in both task sets, we only need to consider the pattern-triggered tasks.

Every instance of a pattern-triggered task τ i from Γ is triggered by an occurrence of some event in prim(E i ). Thus, the activation times of τ i can be mirrored by activations of the corresponding sporadic tasks in Γ aux .

Next, consider an individual instance of τ i , triggered by an occurrence of the primitive event A. If A ∈ term(E i ), then an occurrence of A can never result in a full occurrence of the pattern, and thus the τ i instance only executes the detection algorithm and not the response. This is consistent with the WCET of τ iA , which is de ned as C iA = wcet(E i ) when A ∈ term(E i ). For events in term(E i ), Γ aux safely approximates Γ by assuming that they can result in a full occurrence of the pattern.

Clearly, the execution time of the τ i instance can not exceed wcet(E i ) + C i .

Altogether, this means that any sequence of Γ task instances can be mirrored by an instance sequence of tasks from Γ aux with the same arrival times, priorities and execution times. Thus, if Γ aux is schedulable, so is Γ.

The tasks in the auxiliary task set are either periodic or sporadic, which means that existing schedulability analysis theory [START_REF] Sha | Real Time Scheduling Theory: A Historical Perspective[END_REF] for EDF and FPS, respectively, can be applied.

Example (EDF)

Under the EDF scheduling policy, a given task set is schedulable if and only if no deadline is violated during the busy period. This was shown by Liu

and Layland [START_REF] Liu | Scheduling algorithms for multiprogramming in a hard-real-time environment[END_REF] for task sets where D i = T i , and extended to less restricted task sets by Spuri [START_REF] Spuri | Analysis of deadline scheduled real-time systems[END_REF] and Ripoll et al. [START_REF] Ripoll | Improvement in feasibility testing for real-time tasks[END_REF] independently. For the example system, we have a busy period of length 190, and the following absolute deadlines must be investigated: Example (FPS) In an FPS context, standard response time analysis [START_REF] Sha | Task scheduling in distributed real-time systems[END_REF] can be applied, taking into consideration that deadlines may be larger than periods [START_REF] Lehoczky | Fixed priority scheduling of periodic task sets with arbitrary deadlines[END_REF][START_REF] Tindell | An extendible approach for analyzing xed priority hard real-time tasks[END_REF],

{d | d = kT i + D i , d ≤ 190, τ i ∈ Γ aux , k ≥ 0} = {30,
and that tasks do not have unique priorities. For the example task set, a worst-case response time r i is computed for each τ i in the auxiliary task set: At rst, it may seem that approximating a patterntriggered task by a set of sporadic tasks introduces a lot of pessimism. However, as a result of the algebra detecting also partially overlapping occurrences of a pattern, this over-approximation only happens for a relatively limited number of expressions. In fact, any expression that does not contain negation or temporal restriction can in the worst case occur exactly as often as the auxiliary taskset counterpart. With negation or temporal restriction, it is possible to construct expressions for which the auxiliary taskset is an over-approximation. For example, P -P or (P;P) t when t < mint(P) de ne patterns which never occur, but which are assumed to occur as often as P in the auxiliary taskset.

τ i P i C i T i D i r i τ 1
One way to reduce the over-approximation in such cases would be to simplify the expression, based on the algebraic laws exempli ed in Section 4.3, before constructing the auxiliary taskset.

Conclusion and Future Work

This paper introduces the concept of event pattern triggered tasks, where tasks can be triggered by more complex event patterns than the traditional periodic or sporadic event streams, and shows how such tasks can be realised for existing real-time operating systems without support for pattern detection. Furthermore, we propose an event algebra that is able to express the activation criteria of such tasks. The algebra exhibit several properties that make it useful in a resource constrained real-time setting:

• Algebraic laws The laws show that the algebra corresponds to what one might intuitively expect from the operators, and facilitates analysis and optimisation of event expressions.

• Realisation and implementation The pattern detection code can be automatically generated from the triggering expressions. Moreover, the run-time footprint, in terms of CPU utilisation and memory consumption, is low and statically bounded. The code also exhibits properties that makes automatic WCET calculation by existing tools feasible.

• Schedulability analysis Assuming that constituent events are sporadic, the task set can be transformed into a standard periodic/sporadic task model, which means that standard scheduling theory can be applied. If the result of the transformation is schedulable, then so is the original task set.

To simplify the presentation, we have assumed a fairly simple task model, and shown how FPS and EDF schedulability analysis can be applied. Extending the model to consider precedence constraints, blocking caused by shared resources, etc. should be straightforward, but the details need to be formalised.

The future work also includes investigating alternative ways to specify triggering patterns, for example timed automata [START_REF] Alur | A theory of timed automata[END_REF] or RTL [START_REF] Liu | A uni ed approach for specifying timing constraints and composite events in active real-time database systems[END_REF][START_REF] Mok | Specifying timing constraints and composite events: An application in the design of electronic brokerages[END_REF]. The proposed algebra provides an intuitive high-level formalism for event pattern speci cation, but for some applications a more detailed control might be required.

task τ 2

 2 Figure 1. Realisation of the patterntriggered task τ 2 triggered by the pattern (P+T)-B.

  B. The start-and end time of composite occurrences are de ned as follows: start(a ⊕ b) = min(start(a), start(b)) end(a ⊕ b) = max(end(a), end(b))

4. 3 .

 3 PropertiesNext, we present a selection of algebraic laws showing to what extent the operators behave according to intuition. Moreover, the laws facilitate formal and informal reasoning about the algebra and about tasks triggered by patterns de ned by the algebra. For example, they could form a basis for rewriting event expressions to minimise the resources required for detection.For this, we rst de ne expression equivalence as follows:De nition 4 For two event expressions A and B we de-ne A ≡ B to hold if [[A]] = [[B]] independently of how the primitive events occur.

Figure 3 .

 3 Figure 3. Concrete detection algorithm for (P+T)-B.

Theorem 3

 3 The time and memory complexity of the algorithm is O(m 2 ), where m denotes the number of subexpressions in A.

  mint(P) = 70, mint(T) = 200, mint(B) = 60 and wcet((P+T)-B) = 5.

  r i ≤ D i for all tasks in Γ aux , the original task set Γ is schedulable under FPS.

* This work was partially supported by the Swedish Foundation for Strategic Research via the strategic research centre PROGRESS and by the Knowledge Foundation within the project MultEx.

Persistent and auxiliary variables are initialised as follows: Theorem 2 Assume that the algorithm is executed every tick when some primitive event occurs, and let S denote the set of detected occurrences, i.e., the contents of a m after executing the algorithm, except when a m = ε. Then res(A, S) holds.

Proof: A detailed formal proof is given in [START_REF] Carlson | Event Pattern Detection for Embedded Systems[END_REF].