Eric Brousseau

Tom Dedeurwaerdere

Chapter 1 Global Public Goods: The Participatory Governance Challenges

This book addresses the topic of the governance of global public goods (GPGs). As explained in the introduction, the specific problem in the governance of GPGs is not only their multi-level character, due to the absence of a supreme global political constituency which shapes collective preferences and makes collective decisions. It is also the lack of clear-cut knowledge on collective preferences and solutions. This intricate combination of a collective-choice issue and a cognitive lack makes it worth discussing an analytical framework aimed at disentangling the various dimensions of the questions to be analyzed and debated.

It should not be forgotten that the concept of a global public good is questioned by many people. At first sight the idea that there are problems of concern for all humankind can be considered a heroic assumption, or the result of a set of moral beliefs and assumptions about the necessary solidarity among human beings in a global society that considers their mutual interests. It is worth noting that such concepts can lead to requests that would certainly not be acceptable to some groups. For instance, the developed North could request the South not to develop, so as to preserve biodiversity, slow the process of global warming, and avoid resource depletion. To avoid any criticism of moral (or immoral) bias, we show in this chapter that even if we accept a set of minimal assumptions -starting from self-interested individuals -problems of global concern are raised which should be governed by a combination of political and economic solutions. To put it another way, even if we ignore the potentially altruistic orientations of human beings, the coordination needs of individuals and the existence of biophysical interdependencies on a global scale enable us to identify several issues that have to be dealt with collectively. Among these is the provision of goods of concern for all, which requires mechanisms for collective decision making and the management of motivations so that contributions are guaranteed.

To demonstrate this, we assume a world of individuals who pursue their own ends, but who recognize that they belong to communities in which two types of social relationship are built. On the one hand, exchange is at the basis of many social interactions by which agents align their individual interests through bargaining, ending in quid pro quo transactions. On the other hand, the logic of gifts (without quid pro quo compensation) is at the basis of the social interactions by which agents align their interests by recognizing a common interest encompassing and surpassing individual preferences. The definition of this 'collective interest' can be influenced by players who may push their own interests, but who nevertheless take the interests of other members of the community into account.

The argument presented here aims to provide a roadmap for the analysis of the various dimensions which contribute to the efficient and legitimate provision of GPGs. First we show how the two logics of social interaction generate different types of governance mechanisms that often interact and are hybridized in global governance. We then point out why, in the context of the provision of GPGs, bounded rationality and the global context combine to demand the generation of new knowledge. New knowledge is needed to identify the issues and their possible solutions, and stakeholders have to be made aware of the issues to be able to express meaningful preferences. We also highlight the fragmentation of today's global society into communities without clear hierarchies, and the inclusiveness necessary for processes resulting in compromises about the definition of goods of common and global concern. Finally, we discuss the potential of the principles of reflexive governance and their practical limits. The concluding section shows how the various dimensions of GPG governance analyzed in this chapter are further developed in the five parts of the book.

The Governance Issues Raised by the Many Features of Public Goods

To define the common background of the chapters in this volume, it is important to start with a brief reminder of the basic economics of public goods. We first recall the standard definition and then show how the conventional approach has to be reconceptualized and extended to take into account the multi-level and partially socially-constructed nature of global public goods. This explains why we then develop a theoretical framework aimed at pointing out the challenges raised by the governance of GPGs.

Pure and Impure Public Goods

Public goods are goods of common concern, more appropriately called 'collective goods' (Sandler 2004). They are characterized by the properties of nonrivalry in consumption of the good (their use by one individual does not diminish the possibility of their use by another) and non-excludability (it is costly and sometimes impossible to exclude a user from access to, or use of, the good). Pure public goods are both non-rival and non-excludable. Other types of public goods have only one of these properties: common-pool resources (land, water, livestock, etc.) are partially rival and non-excludable, and club goods (e.g. encrypted TV programs or intellectual property rights) are non-rival but excludable.

Partial rivalry can arise when additional users detract in some way from the benefits available to others, through crowding/congestion costs. Partial rivalry in common-pool resources has been extensively dealt with in the literature on the new commons. For example, in the new globally distributed digital commons (such as the Internet), collective action problems related to partial rivalry (such as a conflict of priorities, overuse and congestion) have been increasingly recognized (Hess and Ostrom 2007). Similar problems of rivalry have been the focus of analyses of the global environmental commons (such as biodiversity and carbon sequestration), because localization and geographical scope brings unequal benefits and costs to stakeholders (Dolsak and Ostrom 2003). Public goods with global and non-exclusive, but partially rival, benefits, thus raise coordination issues that go beyond the problems of free riding and undersupply (see Carraro 2003 for a discussion of global environmental agreements).

In terms of provision, club goods do not pose major collective-action problems, as they can be efficiently supplied by members of the club, financed through tolls or user fees. However, as has been shown for scholarly publications, club goods raise delivery issues (Boyle 2007). The artificial transformation of pure public goods into club goods through the use of (digital, in the case of publication) fences, can produce a major decrease in social welfare. There is therefore a trade-off between the loss of social welfare resulting from the reduced availability of a nonexclusive resource, and the benefits in terms of a reduction in free-riding which increases the contributions to provision.

Heterogeneity in Consumption and Contribution

Other important issues around the provision of public goods are linked to the heterogeneity of benefits and contributions among the various stakeholders. Some goods benefit different actors in different ways. For example a preserved natural area benefits the local inhabitants, but also visitors who come to enjoy the scenery. The area can be used for recreational purposes or it can be managed so that it contributes to the global conservation of biodiversity. In such a context, the nature of the governance solution may impact upon the weighting attached to alternative users' preferences. For instance, pseudo-market solutions may favor wealthy urbanites to the detriment of farmers; 'democratic' mechanisms may mean that local interests prevail over more global or distant stakeholders.

The heterogeneity of contributions leads us to consider the issue of aggregation technology. This refers to how individual contributions to the collective good determine the quality of the goods available for consumption (Hirschleifer 1983;Cornes and Sandler 1984). With summation goods, each unit contributed to the public good adds identically and cumulatively to the overall level of the good available for consumption. For example, any reduction in the emission of greenhouse gases corresponds to the aggregate (summed) cutbacks of the polluter countries. Other important types of aggregation technologies are weakest-link public goods, (where the smallest contribution fixes the quantity of the public good for the entire group, as in pest control), best-shot public goods (for which the overall level of the public good equals the largest single individual provision level e.g. finding a cure for a disease), and weighted-sum public goods (where different contributions can have different impacts, as in the cleanup of polluted sites). The main message of this research is that aggregation technologies other than summation often provide hopeful signposts to feasible collective action to produce the collective good where no state (or alternative coordinator of a large population of individuals) has control, so as to ensure an efficient level of contribution by all (Sandler 2004). In the case of knowledge it is often better to focus efforts on gathering the contributions of the most efficient providers, even when the end product remains freely available to all, as has been shown for free software communities (Nguyen and Pénard, 2007).

Public Goods as Societal Issues

Public good provision is a social issue which raises social challenges. Provision is a social issue because dealing with GPGs is not just a technical/natural problem. Fundamental social choices include the definition of the boundaries of communities and the nature of the social contract, in particular the recognition of social groups within those boundaries. Public goods raise social challenges because the way to deal with them depends upon the design of adequate governance structures, in at least two distinct ways. First, the provision of public goods in general, and of GPGs in particular, raises the question of coordination among different communities and authorities. This is the central issue dealt with by fiscal federalism (see Oates, 1999). However, what is specific to GPGs is that there is no global government to coordinate the various authorities and communities involved in their production. Moreover, the jurisdictions involved in the production of GPGs are of various kinds. There are governments (at all levels), and self-regulated communities of many kinds (from rural communities to international business associations). The specificity of incompletely hierarchized coordination among heterogeneous providers is a true challenge for the social sciences. Second, it is important to stress that many of the properties of rivalry and excludability, and the aggregation technology, are neither absolute nor natural. They partly depend upon processes of social construction. For instance, rivalry in consumption of a good is directly related to population density, and the notion of exclusion is socially constructed and can evolve with the development of new technologies.

A Framework for Analyzing Collective Governance

To understand the properties of alternative models of governance, we need to take into account how complex individuals interact in a society and the logic of alternative governance principles in that perspective. This is why we first highlight a double logic in individual interactions, before pointing out the existence of four basic models of social interaction. These clearly refer to different logics, but in practice they co-exist and are blended in varying proportions in different societies.

Self-interested and Boundedly Rational Individuals

To present our argument, we use an analytical framework derived from new institutional economics (initiated by Coase, North and Williamson; see Brousseau and Glachant 2008 for an overview). We consider global society as a collection of individuals embedded in social structures, who are characterized by individual preferences (which can be collectively built). These individuals have bounded rationality (as defined by Simon 1978Simon , 1986)), and more precisely, procedural rationality. Individuals and collectivities are nevertheless repositories of knowledge. Individuals know how to solve problems (including learning procedures for solving new problems, which is the idea behind the notion of procedural rationality). They also have a social capability to interact with other individuals who can help them to solve problems. The unit of analysis is therefore a collection of individuals, who are both stakeholders and knowledge-holders. They have their own interests, and they also have personal capabilities to solve problems, to learn and to interact with other knowledge-holders.

Individuals have their own set of preferences and ranking among them, depending on their history, beliefs, societal position, etc. These preferences are ordinal and subjective. They therefore cannot be weighted and aggregated to yield a collective preference function (May, 1954;Savage, 1954). An individual's system of preferences is incomplete and therefore unstable. Since their rationality is bounded, individuals can discover new options and therefore revise their whole system of preferences (Simon 1957(Simon , 1983(Simon , 1986;;Selten 1990).

Self-interested individuals are concerned, above all, with the realization of their own ends (according to their own system of preferences). They know that this realization depends upon successful coordination with the other individuals in society. Individuals do not, however, always spontaneously recognize themselves as being members of a local, national or global society that encompasses all living individuals, or even all the individuals leaving in a common territory, or belonging to the same group. To be consistent with the idea that individuals have bounded rationality, idiosyncratic hierarchies of preferences, and specific beliefs, it must be recognized that the concept of society is subjective and has little chance of being implemented consistently in every individual's set of preferences. To put it another way, not everyone has the same vision of what society is, and not everyone shares the idea that humankind per se is a society. This raises the issue of the definition of problems of global concern (see below). While recognizing this, we assume nevertheless that people are social beings. They know that they belong to collectivities. Collectivities are characterized by the existence of common rules of behavior, drawn from the convergent beliefs of members with shared interests, which justify constraints in the name of collective action. These collectivities can be labeled 'communities', to p oint out their subjective aspect and its consequences.

In such a context, governance is not just a question of designing techniques to aggregate preferences (so as to manage collective choices) and implementing incentives to harmonize individual behavior. It also involves producing and sharing information to allow individuals to establish and modify their preferences. Furthermore, governance is about innovating and enhancing the collective capability to influence behavior so that individuals can discover and share new beliefs, more effective ways of resolving issues, and better techniques for confronting problems of collective action.

Four Articulated Models of Social Interactions

Individuals recognize that the realization of their ends necessitates interactions with other members of their communities. At this stage of our reasoning let us consider interactions among individuals in a given community, rather than interactions among communities. Interactions among individuals within a community can be based upon two alternative principles (trade/compensation or sharing/compromise) that are implemented in different ways. According to the trade/compensation principle, an individual agrees to renounce something (the benefit of a good, a right, or even having to make an effort) if and only if he or she is compensated by the provision of a good or service that balances the loss of satisfaction entailed by the renouncement. The sharing/compromise principle states that individuals, while recognizing their individual ends, use the community as a tool for reaching these ends. Individuals contribute to the realization of the ends of the other members of the community and (expect to) benefit in return from the community's contribution to their own ends. Of course free-riding is an issue, but it is not always the best individual strategy and mechanisms can be implemented to control it. Here there are no transactions but only gifts (with the social consequences highlighted by Mauss 1924). Both these principles can be implemented either centrally (by means of collective decision mechanisms encompassing all the members of the community at the same time) or by bilateral negotiations between individuals.

This leads to four models of collective interaction, which have long been recognized and analyzed in the social sciences, and which are characterized in Table 1.1:

 The (neo-classical) social-planner model indicates a situation in which an entity is in charge of optimizing the performance of the social system. This entity should act as a neutral engineer. There is no collective interest per se, but individual interests can be summed. The social planner overcomes coordination difficulties due to information costs, indivisibilities, etc. and thereby allows the maximization of each individual's welfare. It applies a Pareto principle and can organize compensation among individuals à la Hicks-Kaldor to reach a Pareto-improving situation that may harm some members of the society.  The market model describes a situation in which a central, neutral agent cannot emerge, or cannot perform the social-planning task to the benefit of all. All social interactions are organized on a quid-pro-quo basis. Market failures may exist, but alternative ways of organizing transactions also have drawbacks.

 The communism/family model represents the situation in which an elite governs the society for the benefit of all, either because it is enlightened or because it has been consensually chosen. Its aim is to provide goods to each member of the society as a function of their needs, and to request contributions proportional to everyone's means. There is therefore no perfect match for individuals between what they give and what they get, and constraints are required to manage this de facto redistribution. The redistribution can be justified in various ways (ethical principles, political need to strengthen the collectivity or maintain its consistency, economic need to invest in collective resources benefiting everybody, etc.).  The social-networks model refers to settings in which individuals freely choose to contribute to a collective venture without expecting compensation proportional to their contribution. The word 'community' is often applied to such an arrangement (for example, open-source software communities or local communities). Of course, none of the pure principles illustrated by the boxes fully characterizes any real society; while some societies are essentially based on market interactions, others exemplify collective compromises. The principles apply to various degrees in any society/community. This has an impact on the motivations for individuals' actions. It also has an impact, of course, on the logic of governance, which is different in each of the four modes of social interaction.

Disentangling the Logic and the Mechanisms of Coordination

Our goal in this section is to clarify the drivers of individual social behavior. The dominant vision is to contrast two facets of human psychology: selfishness and altruism. The first is a core assumption in economics, and leads to a vision of society in which central coordination is useless (or completely neutral). The second is a core assumption in ethics (and politics). Our analysis shows that both types of interests can be dealt with within either centralized or decentralized institutional systems. This allows us to disentangle the logic of coordination (driven by individual or collective interest) from the mechanism of coordination (which refers to how collective decisions are made). This is useful in understanding the properties of alternative governance mechanisms and institutional architectures.

The first column of Table 1.1 refers to a cost/benefit analysis (managed either at the individual or the collective level), in which collective action is based on the logic of exchange. The second column refers to a universe of ability to influence the behavior of others in which collective action is based on social constraints and conviction. In brief, the first column refers to economics, the second to politics. Since individuals do not perceive the world as either a purely economic or a purely political entity, they understand that the realization of their individual ends relies on both mechanisms.

This results in complex motivations. Individuals have both what are usually called individualistic preferences (which in our nomenclature are economic preferences linked to the logic of transactions) and collective preferences (in our terminology, political preferences linked to the logic of sharing and compromise). Obviously theses preferences differ from one individual to another, and are balanced in different ways for different purposes within individuals. However, individuals clearly have complex motivations because they simultaneously take into account their immediate interest -let us say their individual wealth -and a broader collective interest. They know that the wealth of the community/society impacts on their individual situation. To put it another way, individuals have both exclusive interests (they decide in terms of their own situation) and inclusive interests (they consider the impact of their actions/decisions on other stakeholders in the society and have their own preferences for that society).

Governance in such a framework consists first and foremost of the choice of a social interaction model for a given domain of collective life. Sets of individuals have to agree on the respective domains of self-interest and collectivity in a given society, and on the scope of collective coordination in each of these domains. Then of course, actual governance mechanisms have to be implemented and operated.

Public Goods in a World of Bounded Rationality

There are two categories of problems that individuals have to solve, that, by definition, are collective. The first is the provision of an infrastructure to manage the interactions between them (from a common language to market places, and including the institutional framework in the sense defined by Coase (1988) and North (1990)). The second is methods of managing external effects. External effects occur when, for some reason, the use of an asset by one individual impacts (positively or negatively) on the utility of a non-user of that asset, and it is either technically impossible, or prohibitively expensive, to confine the use of that asset to a particular person or group. What Samuelson (1954) called a public good is simply an extreme case of an externality. A service is automatically provided to everybody, but this provision does not deprive anybody of the benefits of the service.

As even economists of the Austrian school, such as Hayek (1979), recognized, the pure logic of decentralized trade fails to provide these goods because of the free riding which generates the 'tragedy of the commons'. This does not mean that the provision of these goods should rely on an organization called the state. It does, however, mean that there should be a mechanism to force individuals to contribute, either through social constraints or conviction, which applies to all the members of the community who benefit from the good.

It has been well documented, by Ostrom (1990) in particular, that compulsion can emerge spontaneously at the local level. Local communities can control the behavior of their members due to the stability of groups, the repetition of interactions, the high cost of exclusion through ostracism, and the easy diffusion of information on the behavior of members that sustains reputation effects. Spontaneous 'cooperation' therefore flourishes in small, stable groups. However, as well demonstrated and argued by Milgrom, North and Weingast (1990), the larger the group, the more formal and institutionalized the coercion mechanisms must be. In any case, collective goods raise the issue of how the provision of a service which is available to everybody on the basis of mandatory contributions is to be organized.

While the acceptance of formal or more informal means of coercion allows public goods to be provided, the problem of how to select among the many potential public goods those that will actually be provided (assuming that scarcity prevents the provision of all of them) remains. There is also the question of how they should be supplied. In a world of perfectly rational agents (in Savage's (1954) sense) each individual has a complete and stable set of preferences. Individuals are therefore able to value each potential public good, and a benevolent and costless social planner can implement a revelation scheme so that individuals show their preferences in a way -their propensity to pay -that allows their individual preferences to be aggregated.

In a world where agents do not have perfect rationality, however, two problems occur. First, bounded rationality means that agents are unable to value their individual utility for each possible public good according to a common currency. Even if they were able to rank their preferences (which presupposes knowledge of the complete list of potential public goods), in the absence of common currency, a social planner would be unable to aggregate their preferences because the Condorcet-Arrow paradox of social choice would apply (Arrow, 1950). Second, bounded rationality could result in agents ignoring the complete list of potential public goods. In that case, it would be impossible for any social planner to decide which projects should be undertaken on the basis of individual wishes. In such a world, the transaction/trade/compensation model cannot be used to decide the amount and type of public goods to be provided.

In addition, in a world of bounded rationality, the scope of the community concerned by the provision of a public good remains an open question. The very notion of public good carries with it the notion of community. There are two conditions for the existence of a public good in this respect. The members of a community should recognize themselves as such (whatever the purpose/nature and boundaries of the community). In addition, they should recognize that a given good is a public (or collective) resource. The first condition leads each member to accept the legitimacy of constraints placed on him or her by the group. The second one legitimates the constraints that are actually implemented in the provision of a given good.

Thus, in a world of bounded rationality, the provision of a public good necessarily entails mechanisms of governance pertaining to the logic of collective cooperation (column two in Table 1.1), since the aggregation of individual preferences is neither possible nor the only issue.

Public Goods in a Global Context

One of the topics this book seeks to address is the mechanisms by which human beings recognize the existence of global public goods and agree on priorities and on ways to provide them. There are two main topics to be dealt with. First, agents have to recognize the existence of goods of common concern at the global level, which means that they must recognize the existence of a global community (i.e. a community encompassing all (present and future) human beings). We have already mentioned this issue and we will return to it below. Second, agents have to establish a collective hierarchy of preferences for any particular GPG and between this GPG and alternative public (i.e. local public) and private goods. In a world of scarcity there is always competition among the various goods that could potentially be provided. This second topic requires an understanding of two sets of intertwined questions. First, the relationships among (the alternative ways to provide) the various GPGs have to be understood, since if these goods are not independent of each other (i.e. there are complementarities and/or substitutabilities between them), this has to be considered when establishing the hierarchy of preferences. Second, the cost of provision of a GPG, which is in competition with the provision of other goods, is not independent of the establishment of the hierarchy of preferences. Agents have to know the costs (in terms of renouncing the provision of alternative goods) of providing GPGs, in order to take production constraints and the possible interdependencies amongst GPGs into account.

Since we assume that our individuals do not have perfect knowledge, we see any agreement on the type of global public goods to be produced and the way to achieve this end as being not only a problem of the revelation and aggregation of preferences, but also a problem of discovering issues and ways to deal with them. Put another way, while we acknowledge that the alignment of individual interests and the building of compromises is an issue, we also claim that the development of knowledge to identify GPGs, to understand the complex web of causal relationships that link them, and to discover how they can be delivered is another requirement.

Our analysis therefore covers the need to consider mechanisms for building the collective interest in the context of global governance. Beyond multi-stakeholder governance, the issue is to define how compromises, and the definition and hierarchization of GPGs, can be achieved in a world without an entity which can ultimately arbitrate among citizens' interest and settle conflicts among their agents (governments, organizations, political groups, etc.). Governance of GPGs necessarily leads to the logic of the gift exchange contained in the bottom right box of Table 1.1.

The Role of Knowledge Communities in Global Governance

Inspired by the new institutional economics (NIE) approach, we feel that it is unnecessary to analyze alternative institutional frameworks from scratch. We are not working in the framework of 'Nirvana economics' (Demsetz 1969). While we recognize that the notion of communities is linked to individual beliefs, we also recognize that individuals participate in pre-existing communities that are organized on the basis of either jurisdiction or shared interests. Thinking about governance issues should therefore start from the fact that individuals are already grouped into communities, although the global community is not yet fully organized. There are therefore various types of sub-global community in which individuals develop their strategies to have an impact on the provision of public goods in general and global ones in particular.

For the purpose of our analysis, we can distinguish between two types of such communities. First there are those organized on a socio-political basis by a geographically delimited jurisdiction. These communities, which are essentially linked by spatial proximity, are generally made up of individuals with highly heterogeneous preferences. They usually already have formal institutional frameworks to manage this heterogeneity, while providing their members with a set of services. They therefore often benefit from (constitutional) collective decisionmaking mechanisms aimed at governing the community and providing it with an infrastructure for interacting (i.e. a legal and political order). Other communities are organized on the basis of mutually shared interests and/or proximities of preferences.

They group individuals on the basis of the realization of a common end, which can be the advancement of knowledge, the promotion of beliefs, the wealth of the members, etc. While such communities might be very formally organized, they tend to rely more on informal coordination mechanisms since they have to manage less tension linked to divergences and differences among their members.

Since there is no established global community recognized as such by all its members, the designation of a good as a GPG does not result from any agreement among all human beings or from any process of aggregation of their will or consent. Some goods are claimed as GPGs by communities that, on the one hand, consider the externalities among existing communities, but on the other hand have strategies to promote their own interests. Indeed, they can seek to benefit from the contribution of others to providing a good that primarily benefits their community. They can also promote the production of the public good they prefer. One consequence of the subjective nature of GPGs, is that their qualification as global, and the ranking of preferences for them, will always remain open to challenge.

In this context, generating knowledge should allow human beings to benefit from more information about the interdependencies among individual interests through the provision of goods. The more knowledge, the more individual interests will be included in collective choices, and therefore the better the nature and hierarchy of GPGs will be recognized, and the more efficiently they will be produced. In turn, the identification of interdependencies should allow each individual to express more informed preferences, since everyone will have a better understanding of the links between their own and the collective interest. Thus the more knowledge, the more complete the set of individual preferences, which will impact positively on the formation and expression of collective preferences.

Reflexive Governance for Collective Learning about the Provision of GPGs

Since there are no established collective preferences or solutions for the provision of GPGs, the design, choice and implementation of the most appropriate rules should result from a reflexive governance process where multiple actors are involved. The importance of reflexive governance has repeatedly been demonstrated in debates on participatory governance in domestic, regional and local contexts. Numerous approaches have shown the applicability of deliberative formats for solving collective issues, with the inclusion of various stakeholder and citizen groups. Examples include planning cells, citizen juries and consensus conferences. These participatory procedures not only diffuse information, allow for consultation, and support sharing in anticipation of the future; they also support the coordination of different forms and fields of knowledge, and the co-production of solutions, and social learning. While the existing literature has shown that participatory approaches are particularly suitable for integrating various bodies and forms of knowledge, concerns have been raised about their limited legitimacy. The need for direct interaction restricts the number of individuals who can be involved. The representation of different stakeholder groups and their knowledge and interests is possible, but the representation of larger fractions of the population cannot be guaranteed by these procedures. What needs to be further explored, therefore, is whether and how far these and other reflexive governance approaches can play a role in addressing the complex collective choice and cognitive problems involved in the provision of GPGs.

There are two aspects of reflexive governance processes: social and cognitive reflexivity. The first is the dynamic adjustment of collective beliefs among a variety of social actors. For instance, some collective rules result in the involvement of new groups and citizens, and this process transforms and builds new collective preferences. In such a perspective, a mode of governance can be considered as reflexive if it aims at including the perspectives, values and norms of a variety of actors. The second aspect concerns the revision of the cognitive framing; i.e. the representation of the issue and of the governance problem at hand. The issue is to delineate the problems and decisions to be considered. New knowledge can change the vision of the world, the issues to address, the hierarchy of problems to solve, etc., as illustrated by the issue of global warming or the precautionary principle in life sciences.

In general, what seems needed for the legitimate and efficient governance of global public goods is the broadening of our categories of public debate, both through deliberation in international organizations, and through more local forms of participatory governance and the involvement of communities and citizens in collective learning on GPG issues. This does not mean that traditional representative democracy will not be needed in the final decision-making phase, or that markets and hierarchies are not needed in the implementation phase. The implementation of reflexive governance also depends on a variety of mechanisms including regulation, incentive mechanisms and information-based mechanisms. In essence, from our perspective, the appropriate provision of global public goods will require a combination of public ordering, market exchange, public debate and the diffusion of information and knowledge to everybody.

Table 1 . 1 .

 11 Four models of social interaction

				Transaction	Gift
				(trade/compensation)	(sharing/compromise)
				Relationships	among	Relationships	among
				individuals are based on	individuals are based on
				exclusive (individual) interests	inclusive (common) interests
	Centralized
	(collective decisions)
	Relationships individuals are	among organized,	(Neo-classical) social planner	Communism/family/non-profit organizations
	because this increases the
	efficiency	of	managing
	interdependences
	Decentralized
	(bilateral negotiations)	Market	Social networks
	Relationships		among		(gift/counter-gift)
	individuals are spontaneous


Forerunners of Cōḻa meykkīrttis

Emmanuel Francis

As a tribute to Dr. K.V. Ramesh, who has been a forerunner for establishing a dialogue between Indian epigraphists and foreign scholars, I would like to present him this paper about other forerunners from a remote period, those that went ahead of the well-known Cōḻa meykkīrttis. 1 It is commonly supposed that the meykkīrtti genre was invented under Rājarājacōḻa I (r. ca 985-1014) with his famous panegyric beginning with the words tirumakaḷ pōla and appearing from his 8 th regnal year onwards. Meykkīrttis are found mostly at the beginning of stone inscriptions, less often in copper plates. They consist in versified subordinate clauses dependent upon the name of a king, itself generally dependent on an internal date, and are composed in Tamil. [START_REF]For a detailed definition of meykkīrtti[END_REF] The invention of the meykkīrtti under Rājarājacōḻa I was not a spontaneous phenomenon. Actually one can discern a long thread of royal panegyrics in Tamil -starting with the Puṟam poems of Caṅkam poetry -that lead to the meykkīrtti genre. We know for instance of smaller prose "epithets" (strictly speaking subordinate clauses ending with a relative participle) for many predecessors of Rājarājacōḻa I as well as for himself and his successors even after the full-fledged verse meykkīrtti had appeared. [START_REF]About the antecedents of Cōḻa meykkīrttis[END_REF] I here intend to give a more detailed presentation of two particularly important late forerunners of Rājarājacōḻa I, namely Nandivarman III Pallava (r. ca 850) and Kṛṣṇa III Rāṣṭrakūṭa (r. ca 939-967).

Teḷḷāṟṟ' eṟinta Nantippōttaraiyar

A later Pallava king named Nantippōttaraiyar (i.e. "the bull-king" or "sprout-king Nanti") is known in inscriptions as the victor in Teḷḷāṟu. [START_REF] Schmid | Teḷḷāṟu in the Wandiwash tāluk of the North Arcot district (i.e. nowadays Vantavāci tāluk, Tiruvaṇṇāmalai district)[END_REF] His name is the subject of either a relative participle or an absolutive derived from the root eṟi-, itself governing the oblique teḷḷaṟu, standing for a locative. The whole clause means "who cut" (eṟinta) or "having cut (eṟintu) into pieces" or "smashed" or "destroyed (his enemies) at Teḷḷāṟu." The name Nantippōttaraiyar prefixed by this "epithet" is sometimes dependent upon the internal date of the records, but this is not always the case. I have found instances of this epithet in ten Pallava stone inscriptions, sometimes with small variants: 5 Tillaisthānam, Ghṛtasthāneśvara temple (10 th regnal year, seemingly of Nantippōttaraiyar): svasti śrī 7 aṟupatiṉ kaḻañcu..., [START_REF][END_REF] "Prosperity! Fortune! In (his) tenth year, sixty kaḻañcus of refined gold that Nantippōttaraiyar who destroyed (his enemies) at Teḷḷāṟu gave for a sacred lamp to the Mahādeva of the Tiruṉettāṉam..." Centalai, Sundareśvara temple (12 th regnal year, seemingly of Nantippōttaraiyar): svasti śrī [||*] yāṇṭu 12āvatu teḷḷāṟṟu °eṟiñcan 9 nantipp[ō*]ttaraiyar niyamam [ā]kāḷattu piṭāriy [ā]rkku 400 paḻaṅkācu kuṭuttu..., 10 "Prosperity! Fortune! In (his) 12 th year, Nantippōttaraiyar who destroyed (his enemies) at Teḷḷāṟu having given 400 old coins to the Piṭāri of the Niyamamākāḷam..."

[||*] yāṇṭu pa[t*]tavātu tiruṉettāṉattu m[ā*]t[ē*]varkku teḷḷāṟṟ' e[ṟi*]nta na[nta]p[ō*]ttaraiyar 6 tiruviḷakku[k*][ku] [ku*]ṭutta tiypp[ō*]kkucempoṉ

Āṉāṅkūr, on a loose stone found in Āṉāṅkūr and preserved in the J.G. 20 "Prosperity! Fortune! The sixty kaḻañcus of gold that Nantippōttaraiyar who destroyed (his enemies) at Teḷḷāṟu gave to the Mahādeva of Tiruvaiyāṟu..."

Nantippōttaraiyar, victor at Teḷḷāṟu, is also mentioned in an inscription at Lālkuṭi dated to the reign of an unnamed king who must be a Pāṇḍya as shown by the specific "compound" style of the date: svasti śrī [||*] yāṇṭu 4vatiṉ etirām āṇṭu iṭaiyāṟṟu nāṭṭut tiruttavattuṟai māhādevarkku 21 teḷḷāṟṟ' eṟintu veṉṟa nantipp[ō*]ttaraiyar kuṭutta paḻaṅkācu 60tu..., 22 "Prosperity! Fortune! In the year opposite to 4 (i.e. in the fifth year current?), the 60 old coins that Nantippōttaraiyar who, having destroyed (his enemies) at Teḷḷāṟu, vanquished gave to the Mahādeva of the Tiruttavattuṟai in the nāṭu of Iṭaiyāṟu..."

There has been a debate about the identity of this Nantippōttaraiyar who gained a victory Teḷḷāṟu. Some scholars identified him as Nandivarman III who reigned for more than twenty years in the middle of the 9 th century, [START_REF] Srinivasan | For the consensual date of Nandivarman III[END_REF] while others conjectured that he was Nandivarman IV, a supplementary Pallava who outlived the last of the great Pallavas (Aparājitavarman) during the period of nascent Cōḻa hegemony in the first half of 10 th century. This hypothesis of a Nandivarman IV has been put forward by T.N. SUBRAMANIAM (1955, pp. xlviii-lx). He has been followed by K.R. SRINIVASAN (1964, p. 18) and, more recently, by S. SWAMINATHAN (1995; 1998, p. 47). K.R. SRINIVASAN ascribed very precise dates to Nandivarman IV (r. ca 904-926) and considered him as the father of Kampavarman (r. ca 948-980) whereas SUBRAMANIAM (1955, pp. lviii-lix) placed his accession around 925. Several arguments lead these scholars to suppose his existence. SUBRAMANIAM (1955, pp. xlxviii-xlix) argued that some inscriptions attributed to this Nantippōttaraiyar victorious at Teḷḷāṟu mention names referring to Cōḻas of the first half of the 10 th century. [START_REF] Also | [END_REF] The hero-stone at Ceṉṉivāykkāl (SII XII, No. 56; IP, No. 141) mentioned above, which based on palaeography may be dated to the 10 th century, mentions the parāntakapurattu aṟintikai-īśvaragṛha, "the temple of Īśvara (i.e. Śiva) (built by or for) Arintikai in Parāntakapuram." SUBRAMANIAM believed that this temple and this place-name had been named after the Cōḻa kings Ariñjaya (r. ca 956-967) and his father Parāntaka I (r. ca 907-955). 25 He concluded that this inscription cannot be earlier than these Cōḻas and, consequently, that Nantippōttaraiyar cannot be Nandivarman III but is a supplementary and later Nandivarman. Moreover an inscription at Tiruvaikāvūr (SII XII, No. 58; IP, No. 143) dated to the 22 nd year of Nantipmarājaṉ (read Nantivanmarājaṉ, i.e. Sanskrit Nandivarmarāja) mentions Tiripuvaṉamātēviccaruppetimaṅkalam, which is an alternative name of Tiruvaikāvūr known only in inscriptions later than Nandivarman III. 26 SUBRAMANIAM (1955, p. xlxviii) believed this place had been named in reference to the queen of Parāntakacōḻa I and arrived at the same conclusion as with the Ceṉṉivāykkāl inscription concerning the identity of Nandivarmarāja, i.e. that he is Nandivarman IV. SUBRAMANIAM (1955, p. xliii) remarked also that the Karantai copper plates of the 8 th regnal of Rājendracōḻa I (ca 1020) describe Parāntakacōḻa I as having captured the fame, territory, wealth and vehicles of the Siṃhala, Pāṇḍya, Keraḷa and Pallava kings. 27 He concluded that in contradistinction to what was already known, i.e. that Ādityacōḻa I killed the last Pallava king Aparājitavarman, [START_REF]See the Tiruvālaṅkāṭu copper plates (SII III, No. 205, verse 49), the Kaṉṉiyākumari pillar inscription (EI XVIII, No. 4, verse 55), the Cārāla copper plates (EI XXV, No. 25, verse 55), and[END_REF] this Cōḻa king did not wipe out the Pallavas who were able to recover their kingdom for a short time at least. SUBRAMANIAM (1955, pp. xlii ff.) hypothesised then that Nandivarman IV, allied with the Bāṇas and maybe helped by the Rāṣṭrakūṭa Indra III, got back his kingdom (see phraseology of the Ceṉṉivāykkāl inscription: rājyamuṅ koṇṭa) through his victory at Teḷḷāṟu against the Cōḻas. [START_REF][END_REF] He would have been defeated later on by Parāntakacōḻa I and he should be the Pallava referred to in the Karantai copper plates. K.R. SRINIVASAN (1964, p. 12) added that the Vākūr copper plates of Nandivarman III 30 do not mention in connection with him any victory at Teḷḷāṟu, which was manifestly a great feat since it is referred to in Tamil stone inscriptions. This absence confirmed, according to K.R. SRINIVASAN, that Nandivarman III is not the victor at Teḷḷāṟu. SWAMINATHAN (1995, p. 94) further suggested that the Irukkuvēḷ chiefs of Koṭumpāḷūr helped Parāntaka I to defeat Nandivarman IV. His argument is based on the famous Koṭumpāḷūr inscription of Bhūti Vikramakesarin 31 in which this king declares that he made the Kāvēri river red with the blood of the Pallava army (verse 5: kāverīvāri śoṇaṃ samakṛta rudhiraiḥ pallavasya dhvajinyāḥ). SWAMINATHAN noted moreover that the same Bhūti Vikramakesarin in the same verse also claims a victory over a Vīrapaṇḍya (yo vīro vīrapāṇḍyaṃ vyajayata), a king who has been identified as ruling in the middle of the 10 th century. Furthermore an inscription from Kīḻūr 32 dated to the 16 th regnal year of Kōvijaiyanantivikkiramaparumaṉ, whom SWAMINATHAN identifies as Nandivarman IV, establishes that he was a contemporary of Bhūti Vikramakesarin (named Māravam Pūti in the concerned inscription). According to SWAMINATHAN, Nandivarman IV would have taken advantage of the political instability at the end of the reign of Ādityacōḻa I. But after his victory against the Cōḻas at Teḷḷāṟu he would have been vanquished by Parāntakacōḻa I. He might even have acknowledged the Cōḻa authority, if he is the Pallavaracaṉ who offers gold for maintaining a lamp in the 3 rd regnal year of a Parakesarivarman who must be Parāntakacōḻa I in an inscription from Tiruvēṭikkuṭi (SII V, No. 623).

Despite this apparently convincing argumentation, this theory of a Nandivarman IV is open to criticism for several reasons. I will not use arguments based on palaeography in accordance with the advice of our honouree K.V. RAMESH (1984, p. 62) to allow one hundred years leeway for any date fixed on palaeographic grounds. I can sum up my counter-arguments as well as those of T.V. MAHALINGAM (1969, pp. 197-201) in seven points.

First, it is no longer possible to consider -as K.R. SRINIVASAN proposed -this hypothetical Nandivarman IV as the father of Kampavarman, whose date, moreover, is earlier than previously believed. This is made clear through the genealogy available in the Vēḷañcēri copper plates (R. NAGASWAMY 1979) discovered after the Nandivarman IV hypothesis had been advanced. This genealogy clarifies that Nandivarman III is the son of Dantivarman and father of Nṛpatuṅgavarman and Kampavarman, who were rivals. [START_REF] Srinivasan | rejected the Nandivarman IV hypothesis after the discovery of the Vēḷañcēri copper plates. 34. ARE 1927-28[END_REF] Still, this does not preclude the possibility of a Nandivarman IV.

Second, as for the Ceṉṉivāykkāl and Tiruvaikāvūr inscriptions the following remarks have to be taken into account. If the Ceṉṉivāykkāl inscription dates to the 10 th century as its palaeography indicates, it does not automatically follow that this inscription concerns a gift made in the 10 th century. V. VENKATASUBBA AYYAR (1943, p. 23) proposed this date and suggested first that the place and temple of this record were named after the Cōḻa kings Ariñjaya and his father Parāntaka I. Noticing that Nantippōttaraiyar, whom he identified as Nandivarman III, was earlier than these Cōḻas, he concluded that this inscription "therefore appears to be a later copy of the original record." It is remarkable also in this connection that this the only inscription which has the supplementary expression rājyamuṅ koṇṭa. As for the Tiruvaikāvūr inscription, it is beyond doubt a copy as indicated in its eighth and last line (itu kalveṭṭuppaṭi, "this is in accordance with [an earlier] stone inscription"). As the place-name Tiripuvaṉamātēviccaruppetimaṅkalam is otherwise known only in inscriptions later than Nandivarman III, VENKATASUBBA AYYAR (1943, p. 24), who ascribed the Tiruvaikāvūr inscription to the 11 th century on palaeographic grounds, judged that this was not an exact copy. It is thus possible that the Ceṉṉivāykkāl inscription is, like the Tiruvaikāvūr inscription, a copy. Its use of the otherwise unattested expression rājyamuṅ koṇṭa tends to substantiate this view. It is thus conceivable that in both records the temple and place-names were revised at the time of the copy and did not figure as such in the original records. Contra, SUBRAMANIAM (1955, p. xlix) believed that copies are always true to the original and argued that "we have not come across a single instance wherein the text of the original record was altered or tampered with when re-copying." However I do not know of any instances where we possess both an original stone inscription and its later copy which would be required to substantiate this statement.

MAHALINGAM (1969, pp. 199-200), for his part, while considering the Ceṉṉivāykkāl inscription to be authentic and accepting SUBRAMANIAM's statement concerning true copies in relation to the Tiruvaikāvūr inscription, rejected that the names in both inscriptions refer to persons dating to the period of Parāntakacōḻa I. He pointed out that the equation of Arintikai with Ariñjaya is not satisfactory, since the former is a female name; that Arintikai is the name of an Irukkuvēḷ queen of the second half of the 9 th century; that the name Parāntaka is borne by a Pāṇḍya one century earlier than Parāntakacōḻa I; that Tiripuvaṉamātēvi (i.e. Sanskrit Tribhuvanamāhadevī) is also known as the name of the daughter of a Kāṭupattikaḷ Tamarmēttiyār in two records of the time of Ādityacōḻa I. 34 Therefore MAHALINGAM believed that the temple and places in both these inscriptions were named in reference to people prior to Nandivarman III or contemporary with him.

Third, the absence of mention of the victory at Teḷḷāṟu in Sanskrit copper plates is not really a surprise. [START_REF] Also | [END_REF] Sanskrit praśastis indeed refer less often to actual military victories than do Tamil inscriptions. Rather we tend to find there lists of vanquished dynasties in conformity to the ideal of the world conquest (digvijaya). In the case of the later Pallavas I have found mention of actual victories -by which I mean place-names of battlefields -only in five out of the eleven available sets of copper plates. [START_REF]The Utayēntiram copper plates of Nandivarman II (SII II, No. 74; IP, No. 76) exceptionally provide many battlefield names (more than ten) while the other copper plates (SII[END_REF] Fourth, the idea that Nantippōttaraiyar who vanquished at Teḷḷāṟu got his kingdom back through this victory is based on the Ceṉṉivāykkāl hero-stone inscription. But this inscription might not mean that Nantippōttaraiyar got his kingdom back but instead that he got the whole kingdom (rājyam-um). It could be a reference to the recovery of a portion of his dominion at the expense of a vassal who declared independence from the great Pallavas or at the expense of a dynastic rival who encroached on the Pallava kingdom. [START_REF]On the identification of the vanquished king at Teḷḷāṟu[END_REF] Fifth, there is no reason to believe that the verse 17 of the Karantai copper plates has to be taken at face value: it lists four great kings as vanquished in a boasting enumeration, common in royal panegyrics. Moreover none of these kings are named: instead, dynasties are aimed at in a general way. Furthermore these plates describe Ādityacōḻa I in one and a half verse (verses 15 and 16ab) only, while five and a half verses (verses 16ab-21) recount the feats of his son Parāntakacōḻa I. Finally in the short description of Ādityacōḻa I there is no mention that he killed Aparājitavarman or conquered the Pallava country, in contradistinction to other inscriptional records. It is thus possible that the poet of the Karantai copper plates attributed unhistorical feats to Parāntakacōḻa I whether deliberately -in order to minimise the achievements of Ādityacōḻa I and boost those of Parāntakacōḻa I -or by ignorance.

Sixth, if the Kīḻūr inscription proves that a Pallava king named Nandivarman was contemporary with Bhūti Vikramakesarin, he could well be Nandivarman III. As noted by SWAMINATHAN (1995, p. 94), Bhūti Vikramakesarin appears in inscriptions of Ādityacōḻa I (r. ca 871-907). The Vīrapaṇḍya over whom he claims victory in the Koṭumpāḷūr inscription may not be the personal name of a Pāṇḍya king of the middle of the 10 th century but a generic name ("the heroic Pāṇḍya") for any Pāṇḍya of the second half of the 9 th century. It is thus possible that the Pallava king's army with whose blood Bhūti reddened the Kāvēri was not that of an hypothetical Nandivarman IV, but that of Aparājitavarman, the last great Pallava against whom Bhūti would have sided with Ādityacōḻa I. Apparently, after having been a vassal of Nandivarman III as the Kīḻūr inscription seems to indicate, Bhūti sided with the Cōḻas. As for the Pallavaracaṉ of the inscription of Parāntakacōḻa I, there is no certainty that he is a great Pallava. Pallavaraiyar and variants titles were indeed common titles for officers or vassals under the Cōḻas. 38 Seventh, the Lālkuṭi inscription provides the information that Nantippōttaraiyar, the victor at Teḷḷāṟu, is contemporary with an unnamed Pāṇḍya king. This Pāṇḍya has been identified as Varaguṇa I by the editor of this inscription (K.V. SUBRAHMANYA AIYER 1933, p. 51), who fixed the date of his accession in 812. MAHALINGAM (1969, p. 202) thought this Pāṇḍya is Varaguṇa II whose initial regnal year is, according to him, 862. He based his argument on the fact that the Lālkuṭi inscription in question is directly followed by another one -"looking as though it is a continuation of it" and "apparently by the same scribe" -dated to the fourth plus nine year (i.e. in the ninth year of rule as Rāja, after four years of rule as Yuvarāja?) of a Varaguṇa whom he identified as the second one. If this identification is correct, it matches the accepted regnal period of Nandivarman III (around 850). 39 For these seven reasons, I do not subscribe to the hypothesis of a Nandivarman IV living in the first half the 10 th century. I consider that the Nantippōttaraiyar who smashed his enemies at Teḷḷāṟu is Nandivarman III who reigned about the middle of the 9 th century.

If so, Nandivarman III is one of the first kings -in fact maybe the first one -to assume in local Tamil inscriptions a recurrent and specific Tamil "epithet" (namely a subordinate clause ending with a relative participle governed by his name) hailing his military conquest. 40 The use of such epithets is known also for early Cōḻa kings and even for later Cōḻa kings when verse meykkīrttis were in use. For instance, [START_REF]For a longer list of such epithets of Cōḻa kings[END_REF] Vijayālayacōḻa (r. ca 850-871), a contemporary of Nandivarman III, is tañcai koṇṭa, "who took Tañcai (i.e. Tanjore)" [START_REF] See | 111) and, for instance[END_REF] and his grandson Parāntakacōḻa I is maturai koṇṭa, "who took Maturai". [START_REF] See | 121) and, for instance, SII III[END_REF] Such epithets used by Nantippōttaraiyar and early Cōḻa kings can be considered as proto-meykkīrttis. Although short and in prose, they foreshadows the invention of the verse meykkīrtti of Rājarājacōḻa I, that begins with the words tirumakaḷ pōla. This meykkīrtti is in fact an enlargement of a proto-meykkīrtti of Rājarājacōḻa I, namely the shorter epithet (kāntaḷūr) cālai kalam aṟutta (or aṟutt' aruḷiya), which is attested earlier and is incorporated as the third metrical line in the meykkīrtti of Rājarājacōḻa I. It is important to remember that, like such proto-meykkīrttis, proper meykkīrttis too are subordinate clauses ending with a relative participle governed by the name of the praised king.

If one thus considers that meykkīrtti is in fact a verse development of such short prose protomeykkīrttis and agrees that the Nantippōttaraiyar who smashed his enemies at Teḷḷāṟu is Nandivarman III of the middle of the 9 th century, this king could in fact be the one for whom the proto-meykkīrtti was invented, a practice soon to be adopted by the early Cōḻas and later to develop into meykkīrttis. The content of some of the inscriptions where Nantippōttaraiyar is described as victorious at Teḷḷāṟu, i.e. records of his own donations, [START_REF]This is the case explicitly at Tillaisthānam, Centalai, Tiruvoṟṟiyūr, Tiruvatikai, and Tiruvaiyāṟu, and seemingly at Tirucceṉṉampūṇṭi and Tiruppalāttuṟai[END_REF] suggests that he may have been personally involved in the introduction of the proto-meykkīrtti even though one may doubt that these inscriptions are strictly royal (in contradistinction to Sanskrit copper plates).

In any case, the victory of Nantippōttaraiyar at Teḷḷāṟu is not hailed only in Tamil stone inscriptions. It is also referred to many times in the Nantikkalampakam, 45 the earliest surviving example of the kalampakam genre, a poem composed in honour of Nanti, i.e. Nandivarman III. The epigraphical epithet even occurs once verbatim in the Nantikkalampakam. [START_REF]See atteḷḷāṟṟ' eṟinta māṉōtayaṉ in Nantikkalampakam 85[END_REF] Besides this, a peculiar stanza of this poem eulogising Nandivarman III as a warrior stands out as a forerunner of the meykkīrtti of Rājarājacōḻa I. In the stanza 65 of the Nantikkalampakam, presumably genuine and not interpolated because it fits in the antāti scheme, 47 the poet plays with roots that he uses two times with different subjects: If your bright-coloured eyebrows quiver (tuṭikkiṉ), the left side of the kings who do not bow to your feet (literally: anklets) also quivers (tuṭikkum). [START_REF]A left-side shaking is a bad omen[END_REF] If you remove (kaḻikkum) your bright (or: flawless) sword from its sheath, the wives of reluctant (kings) also remove (kaḻikkum) the pearl-ornaments of their ornamented breasts. [START_REF]that Nanti kills all his enemies leaving their wives widowed[END_REF] When conchs similar to your kaṭuvāy ("harsh voice", i.e. Nanti's bellowing war-drum) resound, the determination of the kings who are not on your side falters.

tiruviṉ
If you prepare your big intoxicated elephant(s) (for battle), the blood of the kings opposing you congeals (i.e. their blood runs cold)."

From the metrical, thematic and structural points of view, this stanza recalls the Cōḻa meykkīrttis: it is in āciriyappā, opens with the mention of goddesses as spouses of the king, and mentions a concrete battlefield (Māveḷḷāṟu) where the praised king gained victory. These features are similarly found in the Cōḻa meykkīrttis, which are also set in āciriyappā and consist almost exclusively--after the mention of the goddesses--in the enumeration of victories, if not actually historical at least set in an historical context. 50 If we thus consider the stanza 65 of the Nantikkalampakam side by side with the teḷḷāṟṟ' eṟinta protomeykkīrtti of the stone inscriptions, the epigraphic and belletristic creations produced under Nandivarman III stand out as important forerunners of the meykkīrtti of Rājarājacōḻa I. In this context one has to recall that Cōḻa meykkīrttis are mainly encountered in local Tamil stone-inscriptions, in which the Cōḻa king sometimes plays no other role than furnish a regnal date. Cōḻa meykkīrttis can thus be considered as a development of the Tamil panegyric of Nandivarman III: they are a versified development of epithets like teḷḷāṟṟ' eṟinta and a thematic avatar of a poem like Nantikkalampakam 65.

Kṛṣṇa III Rāṣṭrakūṭa

Approximately one century later than Nandivarman III, we encounter another important milestone towards the meykkīrtti of Rājarājacōḻa I, viz. in a Tamil inscription dated to the 25 th year (963-964) of the Rāṣṭrakūṭa king Kṛṣṇa III. [START_REF]ARE 1939-40 to 1942-43[END_REF] This inscription is engraved on a pillar planted in a field at Caṉikkavāṭi (Pōḷūr tāluk, undivided North Arcot district, today Tiruvaṇṇāmalai district) where I was able to see it in August 2009 on the occasion of an EFEO field trip with N. Ramaswamy and Charlotte Schmid (fig. 2). At the time of our visit, the field had fortunately been harvested, so that we could actually find the pillar. This pillar is 140 cm high (for the portion we had access to, that is from top up to the lowest engraved lines), 33 cm wide and 20 cm thick. Its inscription is entirely composed in āciriyappā. [START_REF]The metre is precisely nēricai āciriyappā according to K.G. KRISHNAN[END_REF] It runs from lines 1-29 on the front face (fig. 34) and from lines 30-57 on the back face (fig. 5). The front face has undergone some deterioration since the Archaeological Survey of India made the impression used by K.G. KRISHNAN (1986): lines 11-12 are now completely missing, while the left portions of lines 13-18 has been trimmed. The back face has been slightly damaged at the beginning of line 32 where the first character is now missing. The inscription reads (fig. 45): 53 (1) svasti śrī ||- Lines 6-15 are unfortunately damaged and full of lacunae. Otherwise we would have at the beginning of this inscription a complete meykkīrtti of an estimated extent of thirteen aṭis. What is striking here in this preserved portion is, on the one hand, its setting in āciriyappā which is the metre of Cōḻa meykkīrttis and, on the other hand, the opening mention of the goddesses, which is a feature common to most meykkīrttis. Moreover it is noticeable also that Tirumakaḷ (i.e. Śrī) is named first, as in the most common meykkīrtti of Rājarājacōḻa I, which starts with the words tirumakaḷ pōla. This unique eulogy of Kṛṣṇa III at Caṉikkavāṭi appears in this regard as the immediate forerunner of the meykkīrtti of Rājarājacōḻa I. [START_REF] Krishnan | [END_REF] It is actually in both content and form a meykkīrtti [START_REF] For | [END_REF] and it could truly have been a direct model for the meykkīrtti of Rājarājacōḻa I. In this connection it is remarkable that Kṛṣṇa III also has a proto-meykkīrtti that is prefixed to his name in inscriptions (kacciyun tañcaiyuṅ koṇṭa, "who took Kacci [i.e. Kāñcīpuram] and Tañcai [i.e. Tanjore]") and that this longer Caṉikkavāṭi eulogy is in fact a much expanded verse development of this proto-meykkīrtti (see kacciyun tañcaiyuṅ koṇṭu in its lines 23-25), in the same manner as the usual meykkīrtti of Rājarājacōḻa I is the elaboration of a proto-meykkīrtti, as we have seen above.

i tiru[maka](2)ḷ muyaṅkac cīrmakaḷ [vi](3)laṅkap ii porukaṭa[l u](4)ṭutta pūtalamu[ḻuva](5)[tu]ñ iii ceṅkō[l] [xxx] (6-10) [xxxxxxxxxxxx] (11) [xx]tta[xxxxxx] (12) [xxx]ṭu[xxxx]{vi?} (13) ḷaṅkiya [xxxxx] ( 14
)

Conclusions

By way of conclusion I will consider the nature of these sources providing forerunners to Cōḻa meykkīrttis. By nature, I mean whether these are literary compositions directly patronised by the eulogised king or creations produced at a local, non-royal level.

While the Nantikkalampakam can be considered as a court poem composed in the royal household of Nandivarman III, one may question the royal character of the epigraphic sources. Were they directly commissioned by the eulogised king or the product of a local initiative? We have seen that some of the inscriptions of Nandivarman III hailing him as victor at Teḷḷāṟu record his own donations of gold. Moreover the number of inscriptions containing this epithet is proportionally high compared to the total amount of the inscriptions of Nandivarman III (more than 20 %). Both observations lead me to infer that Nandivarman III was personally involved in the invention or introduction of a proto-meykkīrtti to these records. As for the Caṉikkavāṭi inscription, which is an isolated instance of a Tamil eulogy of Kṛṣṇa III, it seems plausible that it was composed at the initiative of Nuḷampaṉ Aṇṇikaṉ, the vassal of Kṛṣṇa III whose foundation is recorded in the inscription.

But whoever commissioned these inscriptions, the epigraphic and belletristic production under Nandivarman III Pallava (middle of the 9 th century) and under Kṛṣṇa III Rāṣṭrakūṭa (middle of the 10 th century) stand out as forerunners of the meykkīrtti composed for Rājarājacōḻa I. Nandivarman III as well as Kṛṣṇa III were endowed with proto-meykkīrttis, that is "epithets" that clearly foreshadow fully fledged meykkīrttis. The stanza 65 of the Nantikkalampakam in honour of Nandivarman III and the Caṉikkavāṭi inscriptional poem in honour of Kṛṣṇa III Rāṣṭrakūṭa can be seen as models for the meykkīrtti of Rājarājacōḻa I. These remarkable literary pieces help to bridge the gap between Caṅkam Puṟam poetry and Cōḻa meykkīrttis.

Notes 1 .

 1 I wish to thank the EFEO (French School of Asian Studies) through which a field trip to Caṉikkavāṭi was made possible in the summer of 2009. N. Ramaswamy alias Babu and Charlotte Schmid from the EFEO accompanied me on this field trip. Arlo Griffiths and Whitney Cox read a draft of this paper, making useful comments and polishing my English. My understanding of the Caṉikkavāṭi inscription has been especially improved thanks to many observations made by Whitney Cox. My sincere thanks to all of them.

Fig. 1 :

 1 Fig. 1: Tirucceṉṉampūṇṭi, Caṭaiyar temple. Inscription dated to the 18 th regnal year of Teḷḷāṟṟ' eṟinta Nantippōttaraiyar (SII VII, No. 503; IP, No. 137), lines 1-8. Photo by Charlotte Schmid.

Fig. 2 :

 2 Fig. 2: Caṉikkavāṭi, pillar in a field with inscription dated to the 25 th regnal of the Rāṣṭrakūṭa king Kṛṣṇa III (EI XL, No. 9). Photo by the author.

Fig. 3 :

 3 Fig. 3: Caṉikkavāṭi pillar inscription, front face. Photo by the author.

Fig. 4 :

 4 Fig. 4: Caṉikkavāṭi pillar inscription, front face, i.e. lines 1-29. Photo and computer processing by the author.

Fig. 5 :FiguresFig. 1 :

 51 Fig. 5: Caṉikkavāṭi pillar inscription, front face, i.e. lines 30-57. Photo and computer processing by the author.

Fig. 2 :

 2 Fig.2: Caṉikkavāṭi, pillar in a field with inscription dated to the 25 th regnal of the Rāṣṭrakūṭa king Kṛṣṇa III (EI XL, No. 9). Photo by the author.

Fig. 3 :

 3 Fig. 3: Caṉikkavāṭi pillar inscription, front face. Photo by the author.

Fig. 4 :

 4 Fig. 4: Caṉikkavāṭi pillar inscription, front face, i.e. lines 1-29. Photo and computer processing by the author.

Fig. 5 :

 5 Fig. 5: Caṉikkavāṭi pillar inscription, front face, i.e. lines 30-57. Photo and computer processing by the author.

  Matriculation School at Viḻuppuram (12 th regnal year): śrī [||*] teḷḷāṟṟ' eṟinta nantipp[ō*]ttaraiyarkku yāṇṭu panniraṇṭāvatu..., 11 "Fortune! In the twelfth year of Nantippōttaraiyar who destroyed (his enemies) at Teḷḷāṟu..." Kāñcīpuram, Ulakaḷantaperumāḷ temple (18 th regnal year): svasti śrī [||*] teḷḷāṟṟ' eṟinta nantipp[ō*]ttaraiyarkku yāṇṭu patineṭṭāvātu 12 ..., 13 "Prosperity! Fortune! In the eighteenth year of Nantippōttaraiyar who destroyed (his enemies) at Teḷḷāṟu..." Tirucceṉṉampūṇṭi, Caṭaiyar temple (18 th regnal year): svasti śrī [||*] teḷḷāṟṟ' eṟinta nantipp[ō*]ttaraiyarkku yāṇṭu 18āvatu... 14 (fig. 1), "Prosperity! Fortune! In the 18 th year of Nantippōttaraiyar who destroyed (his enemies) at Teḷḷāṟu..." Tiruvoṟṟiyūr, Vālmīkinātha temple (18 th regnal year): text unpublished. 15 Ceṉṉivāykkāl, on a hero-stone near the ruined gopura of the Śiva temple (21 st regnal year): svasti śrī [||*] teḷḷāṟṟ' eṟintu rājya[mu]ṅ koṇṭa nantipp[ō*]ttaraiyar[k*]ku yāṇṭu irupattoṉṟāvatu..., 16 "Prosperity! Fortune! In the twenty-first year of Nantippōttaraiyar who, having destroyed (his enemies) at Teḷḷāṟu, took the whole kingdom..." Tiruppalāttuṟai, Ādimūleśvara temple (22 nd regnal year): svasti śrī [||*] teḷḷāṟṟ' eṟinta nantipp[ō*]ttaraiyar (y)yāṇṭu irupattiraṇṭāvatu..., 17 "Prosperity! Fortune! In the twenty-second year of Nantippōttaraiyar who destroyed (his enemies) at Teḷḷāṟu..." Tiruvatikai, Vīraṭṭāṉeśvara temple (no regnal year): svasti śrī [||*] tiruviraṭṭāṉattu 18 mahādevarkkut teḷḷāṟṟ' eṟinta nantipp[ō*]ttaraiyar tiruviḷakkiṉukku kuṭutta poṉ..., 19 "Prosperity! Fortune! The gold that Nantippōttaraiyar who destroyed (his enemies) at Teḷḷāṟu gave for a sacred lamp to the Mahādeva of the Tiruvīraṭṭāṉam..."

Tiruvaiyāṟu, Pañcanadīśvara temple (no regnal year): svasti śrī [||*] tiruvai °āṟṟu mahāt[ē*]varkku teḷḷāṟṟ' eṟinta nantipp[ō*]ttaraiyar kuṭutta poṉṉ arupatiṉ kalañcu...,

  pāṭikka[START_REF] Contra | [END_REF] [xxxxx] Sanskrit bhujaṅga) of Kāñcī with strong shoulders that are as high as a mountain [aṭi 16; lines 28-30],Nuḷampaṉ Aṇṇikaṉ, the son (matalai) who gives prosperity 65 [aṭi 17; lines30-32] as the foot (or: feet) of Araṉ (i.e. Śiva) who joins (cēr-tal) with rivers (āṟu)[START_REF] Viz | Śiva loves rivers. See for instance EI I, No. 9[END_REF] -that powerful one (mayintaṉ), (her) lover (kātalaṉ) -gives beauty (teḷi, literally "clearness") to the (many-)sluiced (mataku) Mantākini (i.e. the Ganges)... [aṭi 18-19; lines32-34] 67

	xx	veṇṇe(36)[xx]kalaiyum iruñca (37) [xxxxxx]ṇa (38) [xxxxxxxx]me 59 (39) [xxxxxxxx]vaṅ (40) [xxxxxx]ṟṟu the lover (bhujaṅka, i.e. ...in Kaṭikaimaṅkalam, which is devoid of tumult (or: affliction) (kalakku+ili) and plenty (mali-tal) of arts (kalai) (41) [xxxxxxxxx]laṟāṉ [aṭi 26; lines 47-49], (42) [xxxxxx][m]paramai 60 (43) [xxxxxx]la alias Caḷukkipāṭi, which abounds (mali-tal) in sacred places (talam) which are not shining (tulaṅkā) thanks to (any) liberal donor (vaḷḷal)...giving riches (vaḷan) [aṭi 24-25; lines 43-46], 68
	xxiv vaḷan (44) taru[m][xxx][ke] vaḷḷa(45)l tulaṅkāt in order that it abide (aṟa) (in) the sky (viyaṉ) and get very much (mika) beauty/height (eḻil) in the world like
	(eṉa) a lofty house (maṉai) (made by) Maṉu (i.e. Manu), Maya (architect of the Daityas) and Viccuvakaṉmā (i.e. xxv talama(46)li caḷukkipāṭiy ākiya Viśvakarman, the architect of the Devas) [aṭi 27-28; lines 49-53] xxvi (47) kalaimalikalakkili(48)k kaṭikaimaṅkalattu(49)ḷ (he, i.e. Nuḷampaṉ Aṇṇikaṉ) created (amaittaṉaṉ) a hall (ampalam). So they say [aṭi 29; lines 53-54]. xxvii maṉumayaviccu(50)vakaṉmā nīḷ maṉai(51)y xxviii eṉa mikav ulaki(52)l eḻil peṟa viyaṉ a(53)ṟav 61 (This is) a gift (taravu) that makes Tiru prosper on her red-golden lotus [aṭi 30; lines 55-57]."
	xxix ampalam amai(54)ttaṉaṉ eṉpar
	xxx (55) cempoṟ kamala(56)ttut tiruvaḷar ta(57)rav[ē*]y ||-||-||-
		"Prosperity! Fortune! [line 1]
		So that Tirumakaḷ embraces (him, i.e. Kṛṣṇa III), so that Cīrmakaḷ shines [aṭi 1; lines 1-3],
		so that the entire earth encircled by the dashing sea (is under the protection or authority) of his upright
		sceptre [aṭis 2-3; lines 3-5]
		...shining (viḷaṅkiya?) [lines 12-13]
		...while bringing about (pāṭikka) [line 14]
		(15) tiyoṭu[xxxxx] ...the great earth (mānilam) [line 16]
		(16) ḷa mānilaṅ ka[xxx] ...alias Gajamallaṉ (i.e. he who is a wrestler to the elephants that are the other kings) [line 17]
		(17) gajamallaṉ āṉa [xxxx] ...the glorious Akāḷavaruṣaṉ (Sanskrit Akāḷavarṣa, i.e. he who is an unseasonable rain) [line 18],
		(18) cīr °akāḷavaruṣa{ṉ?}[xxx] the great king beloved of the earth (pritivivallabhamah[ārā]jaṉ) [aṭi 10; lines 19-20],
	x xi	(19) pritivivallabhamah[ārā](20)jaṉ [°ē*]rp poli rājā(21)dhirājaparameśvaraṉ the supreme lord emperor of the kings (rājādhirājaparameśvaraṉ), who abounds (or: shines) (poli-tal) with beauty (ēr) [aṭi 11; lines 20-21], 62
	xii	[ta](22)rātalam pukaḻuñ calaka(23)nalātaṉ Calakanalātaṉ 63 whom the earth praises (or: who is praised [throughout] the earth) [aṭi 12; lines 21-23],
	xiii xiv xv xvi	took (koṇṭu 64 ) Kacci, which is excellent (taku-tal) in beauty (kāṇ) (or: which is pleasing to the eye), and Tañcai kāṇṭaku kacci(24)yun tañcaiyuṅ koṇ(25)ṭ' aṅk' 55 [aṭi 13; lines 23-25]. āṇṭa yāṇṭ' [ō*]ri(26)rupattañciṉuḷ In the 25 th year when he ruled there (aṅku) [aṭi 14; lines 25-26], pal(27)lavar k[ō*]māṉ palla(28)vāparaṇaṉ the king of the Pallavas (pallavar kōmaṉ), the ornament of the Pallavas (pallavāparaṇaṉ, i.e. Sanskrit kall uya(29)r tiṇṭ[ō*]ṭ kāñcibhu(30)[ja]ṅkaṉ pallavābharaṇa) [aṭi 15; lines 26-28],
	xvii nuḷampa[ṉ a](31)ṇṇikaṉ vaḷan taru ma(32)talai
	xviii (°i?)yāṟu c[ē*]r araṉ a(33)[ṭi] mataku mantākani 56
	xix	ki(34)[x]ṟu 57 mayintaṉ kātala(35)[ṟ?]ṟeḷi 58 tara


Yohann Uguen
email: yohann.uguen@insa-lyon.fr

Florent

Design-space exploration for the Kulisch accumulator

Floating-point sums and dot products accumulate rounding errors that may render the result very inaccurate. To address this, Kulisch proposed to use an internal accumulator large enough to cover the full exponent range of floating-point. With it, sums and dot products become exact operations. This idea failed to materialize in general purpose processors, as it was considered to slow and/or too expensive in terms of resources. It may however be an interesting option in reconfigurable computing, where a designer may use use smaller, more resource-efficient floating-point formats, knowing that sums and dot products will be exact. Another motivation of this work is that these exact operations, contrary to classical floating point ones, are associative, which enables better compiler optimizations. This work therefore compares, in the context of modern FPGAs, several implementations of the Kulisch accumulator: three proposed by Kulisch, and two novel ones. These architectures are implemented in a VivadoHLS-compliant C++ generator that is fully customizable. Comparisons targeting Xilinx's Kintex 7 FPGAs show improvement over Kulisch' proposal in both area and speed. In single precision, compared with a naive use of classical operators, the proposed accumulator runs at similar frequency, consumes 10x more resource, but reduces the overall latency of a large dot product by 25x while vastly improving accuracy.

INTRODUCTION

Field-Programmable Gate Arrays (FPGAs) have demonstrated their potential as accelerators for many applications. FPGAs may bypass some of the bottlenecks of general purpose processors, such as instruction decoding, register file contention, register spilling, parallelism limitation, restricted datatypes. This freedom of design comes with a more complex programming model, but high-level programming languages are becoming a reliable option for hardware design thanks to recent improvements in the High-Level Synthesis (HLS) tools.

Ironically, the "high level" languages used for these tools are derivatives of C, which is about the lowest possible language for processors, just above assembly code. This entails all sorts of restriction, in particular when computing with real numbers. Then the datatypes of choice are the few IEEE-754 floating-point types [1], and HLS tools strive to comply with the C11 and IEEE-754 standards. Floatingpoint addition is not associative, which leaves a designer with two choices: either preserve the sequential semantics of the floating-point program being compiled, which prevents many optimisations that an HLS compiler could do; or, enable such optimisations, and obtain numerically different results due to a different accumulation of rounding errors. This article addresses this dilemma in the very common case of sums and sums of products, which is at the core of linear algebra and can become very inaccurate when the size of the vectors increases [START_REF] Muller | Handbook of Floating-Point Arithmetic[END_REF].

It is an active research field. Some previous work address the parallelism issue using standard floating-point adders [START_REF] Sun | A floating-point accumulator for FPGA-based high performance computing applications[END_REF][START_REF] Lin | Cascading deep pipelines to achieve high throughput in numerical reduction operations[END_REF][START_REF] Wilson | The unified accumulator architecture: A configurable, portable, and extensible floating-point accumulator[END_REF] or modified ones [START_REF] Paidimarri | FPGA implementation of a single-precision floating-point multiply-accumulator with single-cycle accumulation[END_REF][START_REF] Luo | Accelerating pipelined integer and floating-point accumulations in configurable hardware with delayed addition techniques[END_REF][START_REF] Bachir | Performing floating-point accumulation on a modern FPGA in single and double precision[END_REF]. A variant of the floatingpoint adder that outputs the rounding error allows to handle also the accuracy issue, but in non-deterministic time [START_REF] Ogita | Accurate sum and dot product[END_REF][START_REF] Kadric | Accurate parallel floating-point accumulation[END_REF]. A third line of research, which we follow here, is to use internal formats that depart from traditional floating-point [START_REF] De Dinechin | An FPGA-specific approach to floating-point accumulation and sum-of-products[END_REF][START_REF] Teufel | FPGA implementation of a decimal floating-point accurate scalar product unit with a parallel fixed-point multiplier[END_REF][START_REF] Sentieys | Automatic Fixed-Point Conversion: a Gateway to High-Level Power Optimization[END_REF][START_REF] Lee | Accuracy-guaranteed bit-width optimization[END_REF].

The present work revisits in this context the exact accumulator design proposed by Kulisch [START_REF] Kulisch | Computer arithmetic and validity: Theory, implementation, and applications[END_REF]. Its core idea, detailed in Section 2, is to remove all sources of rounding errors in a sum of products. This is achieved thanks to an internal accumulator that contains the entire floating-point range. This is quite area-demanding, but the potential benefits are single-cycle accumulation, more aggressive optimizations, and guaranteed accuracy.

Several implementations of this idea are possible, each with several parameters. Section 2 reviews the implementations initially proposed by Kulisch. Section 3 introduces a novel technique for managing one-cycle accumulation of signed numbers that improves both speed and area over Kulisch' proposal. Section 4 introduces a novel pipelined architecture. Section 5 compares these implementations in a fully customizable generator, and Section 6 concludes.

OVERVIEW OF KULISCH PROPOSAL

The main idea of Kulisch was to remove all sources of rounding errors in a dot product. First, one needs an exact multiplier. As reviewed in 2.1 below, it is a classical multiplier with the rounding and normalization logic removed, so is actually simpler a classical floating-point multiplier. Then, the classical floating-point adder is replaced with a very wide fixed-point accumulator whose bits cover the full exponent range of a product. For instance, in double-precision, the weights of the bits in a floating-point mantissa can range from 2 -1022-53 = 2 -1075 to 2 1023 . Therefore, the weights of the bits of the exact product of two such mantissa can range from 2 -2150 to 2 2046 . Kulisch even proposed [START_REF] Kulisch | Computer arithmetic and validity: Theory, implementation, and applications[END_REF] to add even more bits to absorbe possible temporary overflows, leading to 4288 bits of accumulator for double precision.

In the remainder of the article, the accumulator width is denoted wa. As the previous example shows, the minimum size of wa can be deduced from the exponent width we and significand width w f of the input format. Table 1 shows the minimum size of exact accumulators for mainstream formats.

In his book, Kulish suggested three ways of implementing the long accumulator [START_REF] Kulisch | Computer arithmetic and validity: Theory, implementation, and applications[END_REF]. The first uses a long adder and a long shift, and is reviewed in 2.2. It is impractical but for very small formats. The second uses only one short adder, with on-chip RAM containing the segmented accumulator. It is reviewed in 2.4. The third uses small parallel adders, and is reviewed in 2.

Exact floating-point product

The architecture used for the exact multiplier is depicted in Figure 1. Each floating-point number is input as sign, exponent and mantissa. The sign of the result is computed by XORing the input signs. The exponents are added and the mantissa multiplied.

Subnormal management adds very little overhead: for each input, if its exponent field is all zeroes, then the implicit bit in the mantissa is set to 0 (otherwise it is set to 1) and a correction of 1 has to be added to the exponent sum.

For input exponents of we bits, the exact product requires w e = we + 1 exponent bits. The implicit bit is added to input significands of w f bits, leading to mantissas of w f + 1 bits. The product of two such mantissas fits on w f = 2×w f +2 bits. This is the exact product that can be added, unnormalized (its leading bit may be 0 or 1), to the long accumulator.

A standard floating-point number can trivially be converted to this extended format. Therefore, in all the following, the terms "exponent" and "mantissa" refer to exact product exponent and mantissa.

Kulisch 1: Long adder and long shift

In this approach, the architecture contains a register of wa bits and an adder of wa bits. Every input (floatingpoint number or exact product) is shifted, according to its exponent, to the correct place, then added to the long accumulator.

This architecture is impractical but for small FP formats, for two reasons. First, it requires a very large shifter. Second, it requires the addition of wa bits at each cycle, which will be either slow due to carry propagation, or expensive if a fast adder architecture is used. Still, it may be the best choice for very small formats, especially if the context enables small exponent ranges.

Splitting the accumulator into words

All the other architectures split the long accumulator in words of b bits. There are N = wa/b such words. This decomposes the shift operation in two: select the words to

XOR subnormal detection + × M a n t i s s a 1 E x p o n e n t 1 S i g n 1 M a n t i s s a 2 E x p o n e n t 2 S i g n 2 0/1 0/1 MultMantissa MultExponent MultSign we w f 1 1 we + 1 2 × w f + 2
ExactProduct Figure 1: Exact floating-point multiplier which send a mantissa, and shift within a word. If b is chosen as a power of two, b = 2 k , the intra-word shift distance is simply obtained as the k lower bits of the exponent, while the word address is obtained as the w e -k leading bits. This is described in Figure 2.

The shifted mantissa will typically be spread across multiple words: at least two, but possibly more. Precisely, after a shift of maximum size b -1, the shifted mantissa is of size

w f -1 + b, and is spread over S = w f -1+b b
words. Such a split has two advantages:

• The two steps of the shift can be executed in parallel;

• Accumulating an input only requires to add it to S words (Figure 2).

However, there are two issues to address. The first is carry propagation from one accumulator word to the next. This potentially actually requires to update all the words above the S target words. If done naively, this may either require a long delay, or a variable number of cycles , during which the accumulator is not available for further inputs.

The second is sign management: as input mantissa may be signed, they actually need to be either added or subtracted to the accumulator. In case of subtraction the first issue becomes an issue of borrow propagation.

Kulisch 2: Split accumulator in RAM

In this variant, the long-accumulator words are stored in an on-chip RAM.

To address the carry propagation issue, Kulisch uses an array that stores the state of each accumulator word. The state can be one of those three: the word only contains ones (state 1), zeros (state 0) or both (state NA). When a mantissa is added some word number M , the architecture also loads from memory the word M such that the state of M is not 1 and M > M and !∃M , (M < M ) ∧ (M > M ) ∧ state(M = 1). This word M is the one that will receive a carry if produced, in which case the state of all the words between M and M switch from 1 to 0. Subtractions are handled in a similar way, needing borrow bits in addition to the carry bits.

If the RAM word size is equal to S × b, at most two RAM words are required for each accumulation, plus one RAM word for the carry resolution. This requires a three-port RAM, which is expensive. Note that the three writes always access three different cells, and can therefore be performed concurrently without contention.

The main limitation of this architecture is that it cannot be pipelined. An accumulation consists of RAM reads, additions, and RAM writes, and the reads of a new accumulation cannot start before the writes of the previous one are completed.

Kulisch 3: Sub-adders with carries and borrows

This architecture, depicted on Figure 3, instantiates one sub-adder for each accumulator word. These N sub-adders (SA) can work in parallel. Besides, two registers receive the carry and borrow values produced by each SA, and transmit it to the next SA, to be consumed at the next cycle. Thus, the carry propagation is delayed. Carries are partly propagated at each cycle, but it takes N cycles at the end of an accumulation (inputting zeroes) to complete the carry propagation. The N additional cycles are not a problem if the number of data to be added is much larger than N . A more expensive alternative would be to use the SA state array discussed in 2.4. It has not been investigated here.

In practice, each mantissa part, tagged with its destination address A, is sent on an accumulator bus (see Figure 3). This bus spans all the SAs and is composed of S lanes. Each SA Actually, the S shifted mantissa words are first rotated to the S lanes of the bus by a bit of modulo-S logic and multiplexing. This then simplifies each SA, which only has to listen to one of the S lanes.

R0 R1 R2 SA C SA C SA C SA C SA C SA C SA C SA C SA C
This architecture enables accumulation with 1-cycle latency. The loop critical path that limits the frequency is the subword accumulation. In Kulisch version (depicted Figure 4) this accumulation adds one mantissa sub-word, one carry bit, and one (negative) borrow bit. Therefore, each SA has to perform both one addition and one subtraction in one cycle.

PROPOSED ACCUMULATOR 1: SUB-ADDERS IN TWO'S COMPLEMENT

We now introduce an improvement to the architecture described in Section 2.5. Instead of sending the mantissa in sign+magnitude format as in Kulisch proposal, the idea is to send it as a two's complement numbers. This replaces the borrow and carry bits with a single carry bit. It also simplifies the SA (Figure 5), which only requires one binary adder. Essentially, it transfers sign management from the SAs (where it was replicated N times) to a single unit described in Figure 6 directly after the exact multiplier. In two's complement, a negative number must have its sign extended all the way to the most significant bit of the accumulator. Therefore, when a negative mantissa is sent on the bus, the S SA's with the matching addresses add it to their accumulator sub-word, and all the SA's with higher addresses add -1 (a string of ones) to their sub-word. This performs the sign extension of the two's complement mantissa accross the entire floating-point range.

Before recovering the accumulator values, the carries have to be completely propagated in N cycles as previously. At that point, the combination of the SAs contains the exact result of the computation, but in two's complement.

Therefore, the leading zero counter of the Kulisch proposal is replaced with a leading sign-bit counter, and then the result mantissa has to be negated again.

PROPOSED ACCUMULATOR 2: TWO'S COMPLEMENT PIPELINED ARCHI-TECTURE

This architecture essentially pipelines Kulisch' bus. Again,the accumulator is split into multiple SAs, this time each associated to a pipeline stage. It uses two's complement data as per previous section. Figure 7 gives an overview of this architecture's principle, and Figure 8 describes one pipeline stage.

In Figure 7, the pipeline stages are separated by vertical lines. The horizontal line separates the terms to add and the result of the summation. The dotted arrows represents the data propagation between stages at each clock cycle.

The S words of the shifted mantissa are sent to the special stages to the right (numbered -S + 1 to 0). The pipeline also transmits the mantissa sign, as well as the stage where the mantissa needs to be added.

The stages between stage 0 and stage N -S are identical. They add the S mantissas in the current SA whose stage match, plus the carry from the previous stage. This carry does not consists of a single bit. Indeed, the result of the sum is computed over b + log 2 (S + 2) bits. The b lower bits of the results are kept in the current SA, and the log 2 (S + 2) higher bits are the carry sent to next stage.

On both ends of the pipelines, there are S -1 stages that are not identical. They performs the same computation but with fewer terms to sum. otherwise the stage adds 0. It also shows how sign extension is managed. The stage matching the leading mantissa word, after adding this mantissa word, replaces it with -1 (all ones in two's complement) and transmits it to the remaining pipeline stages, which will add them to their accumulator sub-words, thus perform the sign extension.

In order to recover the final result, the same method as in previous section is used.

EVALUATION OF THE PRESENTED KULISCH ACCUMULATORS

The architectures presented in this paper have as parameters the input/output sizes and the SA size b. Therefore, we wrote VivadoHLS C++ compliant generators for these architectures. For comparison purpose, we also implemented the original Kulisch versions -synthesis results in the litterature target older VLSI technologies, which would have made a direct comparison difficult.

All the results are reported for a VivadoHLS program that computes the accumulation of 1000 numbers, then converts the final value back to floating point. All the numbers presented here were obtained with Vivado 2016.3 after place and route, on a Kintex 7 FPGAs.

For all the split accumulators, a first question was to determine the optimal SA size b. This study is summarized in Figure 9. The optimal size is found to be 64 bits in most cases. More detailed data, including the maximum achieved frequency, is presented in Table 3. The results of Kulisch 1 and Kulisch 2 accumulators are given in Table 2; As expected, the Kulisch 2 version as the lowest resource usage but suffers from a very long latency. The Kulisch 1 accumulator has a lower latency but a very high LUT usage.

One can see that the Proposed 2 accumulator performs the worst although it was designed to be the best. The reports shows that the multiple input sum of this architectures cre- ates a long data-path that slows down the entire architecture. Conversely, the proposed 1 accumulator performs the best, both in terms of frequency and in terms of resources.

There is also a small trade-off between frequency and resource consumption when varying the SA size.

Finally, it is interesting to compare the best accumulator for single precision with the naive alternative of performing the accumulation in double precision. The Proposed 1 accumulator requires 5x the resources, but brings in a 30x latency improvement. Techniques from the literature that attempt to reduce the latency [START_REF] Wilson | The unified accumulator architecture: A configurable, portable, and extensible floating-point accumulator[END_REF] require much more than 5x resources. Besides, the Kulisch accumulator has guaranteed accuracy whatever the number of terms to add.

Similarly, computing with half-float becomes much safer with a long accumulator, actually safer than switching to

Resources

DSPs Latency Kulisch 1 58129L + 59932R 9 9233 Kulisch 2 2814L + 1919R 9 68173 (SA=64) Table 2: Synthesis results of the Kulisch accumulators from 2.2 and 2.4 for 1000 accumulations with double precision floating-points as inputs single precision (as long as the small exponent range is not a problem), and for a comparable cost.

In the state of the art, only [START_REF] Kadric | Accurate parallel floating-point accumulation[END_REF] also addresses both accuracy and performance. Its setup is quite different, but it also requires floating-point memory covering the whole exponent range, with many more shift and normalization steps than in the proposed accumulators. It is therefore even more expensive. It also requires a lot of control, and its actual timing is dependent on the inputs. However, it is able to process in parallel the equivalent of N floating-point numbers in O(log N ) time. Comparing these two approaches in a realistic setup is quite challenging. We hope to do it in the future.

CONCLUSION

This paper presented several implementations of the Kulisch accumulator, an expensive but low-latency and highly accurate implementation of sums of products. These architectures allow to compute exact floating-point sums-of-products, whatever the size of the data.

The proposed two's complement implementation of the split architecture can run at higher frequencies for a lower resource usage than Kulisch' original proposal. It is very competitive in terms of performance/cost/accuracy compared to naive use of floating-point.

Further work include integrating this work in an easy-touse HLS flow. Compressor trees [START_REF] Kumm | Pipelined compressor tree optimization using integer linear programming[END_REF] should also be investigated for the pipelined accumulator.

This work could also be evaluated in the context of VLSI circuits, for inclusion in general purpose processors.

Figure 2 :

 2 Figure 2: Shifting a mantissa into the sub-words of the long accumulator (here S = 3)

Figure 3 :Figure 5 :

 35 Figure 3: Kulisch 3 accumulator for S = 3

Figure 6 :

 6 Figure 6: Two's complement conversion before accumulation

Figure 8 Figure 7 :

 87 Figure 7: Pipelined accumulator for S = 2

Figure 8 :

 8 Figure 8: One pipeline stage for S = 2

Table 1 :

 1 Accumulator sizes for the IEEE-754 formats

	5.
	format	bmin	bmax	min wa
	binary16 (half)	2 -24	2 15	80 bits
	binary32 (single)	2 -149	2 127	554 bits
	binary64 (double) 2 -1074 2 1023 4196 bits

Double LUTs

SA size (log2)