Elias Sheybani

Mitra Zeraatpishe

Are reading comprehension tests composed of different test formats unidimensional?

Keywords: Cloze Test, Exploratory Factor Analysis, Method Bias, Reading Comprehension Ability, Unidimensionality Assumption

. In this research the role of method facet in reading comprehension tests is studied. Bachman divided method facet into five categories, one category is the nature of input and the nature of expected response. This study examined the role of method effect in the Iranian University Entrance Exam (UEE). Research showed the current test method of assessing reading can highly impact test takers' performance and thereby examinees' test scores. Hence, different test formats may extract various traits and therefore, contaminate test scores and threaten validity. The researchers using exploratory factor analysis (EFA) extracted a second method factor in the reading comprehension section of the UEE which is composed of a multiple-choice cloze passage and multiple choice questions based on sustained texts. Results of the analysis showed that cloze test can create construct-irrelevant method variance, contaminating test scores, and led to violation of the unidimensionality assumption of the test.

Introduction

Within an educational setting, students are often evaluated on how much of the assigned materials have been mastered. During the evaluation procedure, they have to cope simultaneously with the content of the test on one hand and the format of the test on the other. A test can take different formats including multiple choice, cloze, matching, true/false, short answer, and essay. Although different in the formats, they share a commonality in that the items have a stem which represents a problem to be solved, but they differ in the subject matter they present (Crook, 1988). For example, in the constructed response questions, examinees must create their own answers which might be a diagram, a short answer, an essay, or an explanation of a procedure (Lukhele, Thissen, & Wainer, 1993). [START_REF] Bachman | Language testing in practice: Designing and developing useful language tests[END_REF] state that characteristics of test methods and formats affect examinees' scores to some extent. They further suggest that it is impossible to prevent the effects of test methods, so it is necessary to control them, as much as possible. There are so many factors that commonly affect examinees' performance like test formats. [START_REF] Bachman | Language testing in practice: Designing and developing useful language tests[END_REF] argues that test score is affected by three major systematic factors, target ability, test method facets (i.e. characteristics of the formats used to elicit knowledge or ability), test takers' personal attributes (i.e. testees' individual or group characteristics). In this research, the aim is to examine the impact of test method facets. Among the most popular test formats in assessing reading are cloze format and reading comprehension questions which are based on sustained passages are the most popular test forms.

Reading Comprehension Assessments

Reading comprehension is an essential component of learning [START_REF] Francis | Dimensions affecting the assessment of reading comprehension[END_REF]. Individuals who experience difficulties reading and understanding information tend to suffer from problems in school in the workplace and in their communities (National Center for Education Statistics, 2002;National Reading Panel, 2000). Not only formal education is difficult for these individuals, but also is the opportunities to reflect, share ideas, and reason effectively. The salience of gaining reading ability brings to mind the concept of assessing such ability. Among several types of tests to measure reading comprehension ability are text comprehension multiple-choice items based on sustained passages and cloze test items. These two test types are used in international language tests, such as Cambridge English tests including First Certificate in English (FCE), Certificate in Advanced English (CAE), Certificate of Proficiency in English (CPE), Cambridge Preliminary English Test (PET) and also in the Michigan Test of English Language Proficiency (MTELP). These international tests should be reliable and reliability with no unidimensionality is of limited value because we do not know what we are measuring [START_REF] Van Der Heijden | Unidimensionality and reliability under Mokken scaling of the Dutch language version of the SF-36[END_REF]. So, if a test seeks to be reliable, unidimensionality is inevitable. Unidimensionality in reading assessments composed of multiple-choice text comprehension items and cloze items can be simply expressed as the loading of all items regardless of the format on a single factor [START_REF] Hambleton | Fundamentals of item response theory[END_REF].

Unidimensionality Assumption

As Hambleton (1992, p.912) explains, "unidimensional scores are what (a) underlying examinee performance on a test is a single ability or trait, and (b) that the relationship between examinee performance on each item and the ability measured by the test can be described by a single factor which is the ability of examinee to answer questions". However, "no measurement is purely unidimensional, there are always some other unwanted factors that contaminate the measurement" (Baghaei, 2009, p. 22). Some findings showed that methods of assessing reading comprehension affect students' scores [START_REF] Kastner | Multiple choice and constructed response tests: Do test format and scoring matter?[END_REF]. Validity, however, is defined based on two issues, what to test and how to test (Bachman, 1995). What refers to the construct and how refers to the test method and if the method affects the construct, the validity of the test is blemished. However, many researchers argued that the methods we use to measure language ability influence performance on language tests (Bachman & Palmer, 1982;Brutsch, 1979;[START_REF] Clifford | A Sisyphean Task: Historical Perspectives on the Relationship between Writing and Reading Instruction[END_REF][START_REF] Shohamy | Does the testing method make a difference? The case of reading comprehension[END_REF]. [START_REF] Bachman | Fundamental considerations in language testing[END_REF] model of language ability (later revised in [START_REF] Bachman | Language testing in practice: Designing and developing useful language tests[END_REF] draws our attention to some factors that can have effect on test performance and, therefore, can jeopardize test validity. According to [START_REF] Bachman | Language testing in practice: Designing and developing useful language tests[END_REF], one factor is the method of assessment itself. Hence, the problem resides in the fact that uncontrolled method factors can have great effects on a test, as several researchers have demonstrated that method bias can inflate, deflate, or have no effect on the estimates of the relationship between two constructs (e.g., [START_REF] Baumgartner | Response styles in marketing research: A crossnational investigation[END_REF][START_REF] Cote | Measurement error and theory testing in consumer research: An illustration of the importance of construct validation[END_REF][START_REF] Podsakoff | Common method biases in behavioral research: A critical review of the literature and recommended remedies[END_REF][START_REF] Siemsen | Common method bias in regression models with linear, quadratic, and interaction effects[END_REF]. In this research, in a combination of cloze and sustained passage comprehension items, we expect to find a single reading comprehension factor and no method factor is expected to emerge.

Method Bias

Literature Review

Some researchers [START_REF] Alderson | Thy: test is unfair: I'm not an economist[END_REF][START_REF] Taillefer | Strategies for professional reading in L1 and L2[END_REF] have assumed that cloze test provides valid measurement of reading comprehension skill argue that some test formats, like open-ended questions, can introduce an unwanted nuisance factor into the measurement.

They conclude that a unidimensional scaling is not appropriate when different test formats are used in a reading comprehension test (open-ended and multiple-choice), and whenever a multidimensional scaling of reading proficiency test is intended, more open-ended items have to be included. The validity of the cloze method for assessing reading comprehension ability has been generally accepted for over 50 years due to the correlations between cloze scores and results of other formats of assessment reported by [START_REF] Bormuth | Comparable cloze and multiple-choice comprehension test scores[END_REF], 1968a, 1968b), Tayl. Rauch and Hartig (2010[START_REF] Jenkinson | Selected processes and difficulties of reading comprehension[END_REF], Rankin (1959), and others. Results of some research support the construct validity of cloze tests, by reducing potential sources of bias (e.g. poor wording of questions, ambiguity in recalls, unrepresentativeness of coverage, delayed inference) in other forms of reading assessment (Bormuth, 1968a(Bormuth, , 1968b(Bormuth, , 1975;;[START_REF] Gilliland | Readability[END_REF]Klare, 1984;Rye, 1982;[START_REF] Ulijn | Communicating in business and technology: From psycholinguistic theory to international practice[END_REF]. However, several researchers have gained different results and also they challenged the validity of cloze tests. Levenston, Nir and Blum-Kulka (1984) clarify the problem by demonstrating that higher reading skills and global coherence can be clearly assessed only if the placement of deletions is deliberately designed. Given these arguments, it seems reasonable to ask whether cloze tests provide a valid measure of the reading comprehension skill.

The mentioned assumptions reveal that test method can highly affect reading comprehension scores. [START_REF] Keenan | Reading comprehension tests vary in the skills they assess: Differential dependence on decoding and oral comprehension[END_REF] concluded that, although format differences underlie the differences between the tests in their sensitivity to word decoding skills, they are not the format differences that researchers have previously focused on. Previous research has simply suggested that cloze tests differ from other reading comprehension tests [START_REF] Francis | Dimensions affecting the assessment of reading comprehension[END_REF][START_REF] Nation | Assessing reading difficulties: The validity and utility of current measures of reading skill[END_REF]. Thus [START_REF] Keenan | Reading comprehension tests vary in the skills they assess: Differential dependence on decoding and oral comprehension[END_REF] primarily proved test format is another factor besides reading comprehension, and scores are heavily influenced by this factor. A recent research through factor analysis reported by [START_REF] Weaver | A factor analysis of the cloze procedure and other measures of reading and language ability[END_REF] showed that comprehension and cloze tests had their largest factor loadings on separate factors and they had only slight to moderate loadings on the same factors. They concluded that cloze test scores do not appear valid. However, much of the research has shown the exact opposite results, that is, scores on cloze tests are highly correlated with scores on standardized tests of reading comprehension ability. For example, [START_REF] Jenkinson | Selected processes and difficulties of reading comprehension[END_REF][START_REF] Balow | The effects of three types of grouping on achievement[END_REF]), and Bormuth (1965) all found correlations which ranged from .70 to about .85. Where lower correlations were observed by investigators such as Fletcher (1955) and Rankin (1957), their size could be explained by the reliabilities of the tests administered and the use of their samples.

Unfortunately, despite the effect of method on scores that has been expressed, there is little agreement about whether it is really a problem or not. Many authors believe that method bias is an important problem that needs to be controlled (e.g., [START_REF] Baghaei | Modeling local item dependence in cloze and reading comprehension test items using testlet response theory[END_REF][START_REF] Campbell | Convergent and discriminant validation by the multitrait-multimethod matrix[END_REF]Cote & Buckley, 1987[START_REF] Cote | Measurement error and theory testing in consumer research: An illustration of the importance of construct validation[END_REF][START_REF] Doty | Common methods bias: does common methods variance really bias results?[END_REF][START_REF] Podsakoff | Common method biases in behavioral research: A critical review of the literature and recommended remedies[END_REF]Podsakoff & Organ, 1986;[START_REF] Sharma | Comorbidity of auditory processing, language, and reading disorders[END_REF], some claim that it is not real (e.g., [START_REF] Chen | Negative affectivity as the underlying cause of correlations between stressors and strains[END_REF][START_REF] Spector | Common method variance or measurement bias? The problem and possible solutions[END_REF]. This research is going to study the unidimensionality of a reading comprehension test composed of MC cloze tests and MC sustained text comprehensions items.

As Baghaei and Aryadoust (2015) argued, if the unwanted dimensions of cognitive and personality factors are as strong as the reading comprehension factor, students' scores are incomparable. A measuring instrument must not be seriously affected in its measuring function by the method of measurement. To the extent that its measuring function is so affected, the validity of the instrument is limited [START_REF] Baghaei | Modeling multidimensionality in foreign language comprehension tests: An Iranian example[END_REF]. EFA analysis is a suitable method to show whether the reading comprehension test composed of MC cloze tests and MC sustained text comprehensions items is unidimensional or there is a method bias in reading assessments. The findings of this research might be contributing to test development, so that test developers could consider influential factors to design a valid test. They should pay attention to factors which might influence examinees' scores. Method of assessing itself, is one major factor, hence it is crucial to test developers to pick the most appropriate method.

Method

Participants and Setting

The participants of the present study were among high school graduates (year 2011) who desired to pursue their studies for a bachelor degree of English in Iranian state universities. These 1024 students contained 23% male and 77 % female. For this study, the researcher used UEE data by the permission of National Organization of Educational Testing of Iran. In order to solve the problems related to student selection, researcher got the permission of the center of test assessment called Sanjesh Organization. The University Entrance Examination (UEE) is specific for English studies and is held on a yearly basis.

Materials and Procedure

University Entrance Exam (UEE) is a test developed for BA candidates in English. This test includes 6 sections of grammar, vocabulary, sentence structure, language functions, cloze test, and reading comprehension; containing 10, 15, 5, 10, 10 and 20 items, respectively. The reading comprehension section and the cloze section were selected for this study. This section consisted of three passages included general knowledge in B1 level. The number of items for the text comprehension questions is 20 and for the cloze is 10. All data were gathered from UEE examinees which contained reading comprehension items and cloze test items. All items were analyzed by 'psych' (Revelle, 2011) package in R software. The examinees' data was taken by the permission of Iran's Sanjesh Organization, a subsidiary of Iranian Ministry of Science, Research and Technology. Exploratory factor analysis was used to study the test dimensionality and its factorial structure.

Data Analysis

Kaiser-Meyer-Olkin Measure of Sampling Adequacy (KMO) revealed that the sample size is good for this study with a value of 0.943. Garson (2002) argued that KMO is acceptable if it is over 0.60. [START_REF] Maccallum | On the practice of dichotomization of quantitative variables[END_REF] argued that factor-to-variables ratio should be no lower than 5; however, in this study the ratio is 34.13. As Figure 1 shows parallel analysis suggests that the number of factors are two. The eigenvalues of each factor is shown in Table 1.

It seems logical that noteworthy factors should have eigenvalues greater than 1.0, as Figure 1 shows the third factor has eigenvalues lower than 1.0. Only for two factors the eigenvalues in actual data are greater than the eigenvalues of the resampled data. So, logically two factors are found to be noteworthy.

Figure 1: Eigenvalues of tetrachoric matrix

Table 1

Factors' Eigenvalues in parallel analysis

Factors Eigenvalues

Factor 1 13.61

Factor 2 1.16

Factor 3 0.71

The number of factors identified by the parallel analyses was two for our data (N=1024)

.

Exploratory factor analysis with two factors was run on the tetrachoric correlation matrix because the items were dichotomous. Factors loading on the two factors are shown in Table 1.

Tucker Lewis Index (TLI) of factoring reliability with 30 items was 0.93. Absolute fit indices including the root mean square of the residuals (RMSEA) indicated the result is reliable. Root mean square of the residuals (RMSR) was 0.05. The RMSEA ranges from 0 up to 1.00, with smaller values indicating better model fit and here 0.05 shows the model is well fit, also a value of .06 or less is indicative of acceptable model fit, so the model is well accepted too.

As Table 1 shows, cloze items mostly loaded on the second factor. Items from 1 up to 10 are cloze test items and items 11 up to 30 are reading comprehension items based on sustained passages. The study indicated that, a reading comprehension test, composed of cloze and sustained passages followed by some questions, is not unidimensional; therefore, this type of test which is currently used in FCE, CAE, CPE, PET, and so many local and global exams may not be valid. Results show that loadings of the cloze items on the second factor are higher than their loadings on the first factor which is the reading comprehension ability factor. Since the results were confirmed by high reliability of raw alpha, the researcher names this second factor as cloze method factor. The first ten items have higher loading on the second factor than the other items, only two items load on the first factor; however, the differences between loadings are not high.

A question arises itself, that whether the second factors influencing the test results could be due to the difficulty or easiness of the cloze items. To answer this question, Figure 2 displays the item difficulty of the whole exam. Figure 2 shows that in X axis the difficulty of all items\questions, both part of reading comprehension test, the first tenth questions and the next 20 questions are almost equally difficult. Y axis says the amount of information each question contains; the more information it has, the harder it become; however, they are almost at the same Level of information. Matrix for this analysis is based on how much these 1024 participants answered questions correctly. The raw alpha reveals that the factor reliability and as shown for the first factor is 0.83 which is upper than 0.70. The results of the second factor analyzing are displayed in Table 3: Based on obtained results in Table 3, the raw alpha for the second factor is 0.84.

Findings showed that the combination of cloze test items and reading comprehension items is not unidimensional. The first reason that comes to mind is that it might be an artifact of difficulty, i.e., the reading and cloze item may have different difficulty. However, results

confirmed that both formats have the same difficulty and the cloze is not easier than the other format, so the extracted factors should not be attributed to difficulty. [START_REF] Hambleton | Fundamentals of item response theory[END_REF] explanation about unidimensional scores is already mentioned that a test should measure examinee performance on a test as a single ability or trait, it means that the best result from 1024 participants should not have more than one factor on which all items load The second characteristic of unidimensionality is the relationship between examinee performance on each item and the ability measured by the test can be described by a single factor which is the ability of examinee to answer questions. However, in this research, the results clearly confirmed another ability or trait which was measured by reading comprehension test. Cloze items had only two questions loading on the reading comprehension factor, i.e., measuring reading ability, the eight other items measured cloze factor. Therefore, format has an impact on unidimensionality of a test either RC items or cloze test items.

Based on Haladyna (2004), sources of construct irrelevant variance include test wiseness, poorly constructed questions, guessing, item bias, indefensible passing score, testing irregularities.

When a test contains flawed items, 'noise' is represented in shape of misleading, and confusing questions that make it harder for the student to answer correctly, even if the student has already mastered the questions' content domain. Flawed questions or items are likely to produce 'false negatives' or they are indication of students who failed the examination but should not have failed. The test wise student can use flaws in the structure of items to get the correct answer without even knowing anything about the content of a questions. These types of questions lead to guessing, and may reduce the chance of picking the correct answer.

Discussion

The main purpose of this study was to investigate whether a reading comprehension test composed of cloze item and MC questions based on sustained passages is unidimensional or not.

Findings revealed that the cloze test created irrelevant variance which was different from the reading variance created by the sustained passages and cloze items combined. The nature of this auxiliary construct is not known. It might be called the ability to handle cloze format, a sort of verbal intelligence [START_REF] Baghaei | The C-Test: An integrative measure of crystallized intelligence[END_REF] or simply local dependence [START_REF] Eckes | Using testlet response theory to examine local dependence in C-Tests[END_REF][START_REF] Baghaei | A comparison of three polychotomous Rasch models for super-item analysis[END_REF]. Future studies should investigate the nature of this nuisance dimension using confirmatory factor analysis or multidimensional item response theory models [START_REF] Baghaei | The application of multidimensional Rasch models in large scale assessment and validation: An empirical example[END_REF]Baghaei, 2013).

Construct-irrelevant variance of cloze test is extremely high, UEE language exam of 2011 reading section was used, the test design was the same as the other tests administered in the previous years. Based on Manhattan reviews, Educational Testing Service (ETS) has revised the TOEFL a numerous of time since the exam was first created in 1964. These changings meant to make the TOEFL more valid and also minimize the construct-irrelevant variance. One of the recent changes is deleting ineffective sentence completion exercises and replacing them with assessments of written English that required understanding of context. These changes make TOEFL (IBT) to be considered as one of the most standardized tests, and international students benefit from an exam that much more effectively demonstrates their ability in English-speaking world. To see all changes in reading section of TOEFL you may need to consult the Manhattan review for TOEFL changes.

The theoretical framework for this study was twofold, first of all it was a research in the areas of language testing and reading. In the zone of language testing, Bachman's (1990) language ability model (later revised in [START_REF] Bachman | Language testing in practice: Designing and developing useful language tests[END_REF] was the main focus. The researchers mainly focused on Bachman discussions, 'method facets' as well as 'trait facets', also they tried to draw attentions to a range of factors that can affect test performance and as a result, jeopardize validity of the test. According to [START_REF] Bachman | Language testing in practice: Designing and developing useful language tests[END_REF], method facets can be divided into five main categories; namely test rubrics, testing environment, the nature of input, the nature of the expected response and, the interaction between input and response. This research focused on the nature of input and the nature of expected response by manipulating test format and organization that plays a significant role. Test methods are unwanted variance associated with the way observations were made rather than with the construct of interest (Maul, 2013). Therefore, method variance is an instance of construct irrelevant variance [START_REF] Messick | Intergroup relations[END_REF]) and a source of test invalidity. Bachman (1990, p. 156) stated that "When test performance is unduly affected by factors other than the ability being measured, the meaningfulness or validity of score interpretations is lessened." This study suggests that examination of the structure of reading comprehension test batteries composed of different test methods, especially cloze format, using a latent trait model is an important steps in validation (Baghaei & Tabatabee Yazdi, 2016).

The result of this research contains an important contribution to testing practice because the number of studies which have examined the effect of factors on examinees seems to be limited, especially in the second language. The findings suggest that examiners of second language ought not to choose formats of comprehension tests simply because of assuming that all formats measure the same trait or ability, they must be aware of the potential effects of test formats on examinees' performance. In this way, test scores will be more reliable and meaningful. It is important for teachers and examiners to identify the exact nature of different test formats. Each format may measure an ability not totally related to language ability. Furthermore, the result of this research stated that different test formats seem to measure different aspects of reading comprehension. This has been already stated in the literature and also confirmed by the present study. The findings are contributing to the test development process because it clarified the complex nature of reading comprehension questions. Syllabus designers should also make a revision of reading exercises they have put in syllabi. It is highly recommended for language testers to conduct in-depth qualitative analysis of test items and questions for expert judgment in examinees' scores. This is particularly very urgent in contexts where examination results have very strong impact on test takers' lives for example, university entrance exams or even CPE.

Test results are used to make major decisions for educational purposes, they play an important role in many applied linguistics research projects. The level of examinees' proficiency should be discussed here, since our data has good variety in proficiency level, the researcher can conclude the results are more reliable than other tests. Because examinees in other tests, like CAE, are almost upper-intermediate, so the result may not be valid enough to generalize. This research has demonstrated that there is another factor in students' test performance. It is, therefore, very important for language testers and teachers, or anyone involved in the assessment, to pay attention to the test methods they use.

Figure 1

 1 Figure 1 Items' loading

Table 1

 1

	Items Loading on each Factor
	Items	Factor1	Factor2	Items	Factor1	Factor2
	V1	0.17	0.59	V16	0.73	0.28
	V2	0.39	0.65	V17	0.68	0.38
	V3	0.23	0.67	V18	0.58	0.34
	V4	0.46	0.62	V19	0.55	0.16
	V5	0.31	0.77	V20	0.71	0.24
	V6	0.29	0.76	V21	0.55	0.44
	V7	0.25	0.58	V22	0.69	0.39
	V8	0.57	0.25	V23	0.36	0.37
	V9	0.52	0.49	V24	0.66	0.18
	V10	0.42	0.47	V25	0.63	0.38
	V11	0.61	0.45	V26	0.52	0.22

Table 2

 2 Reliability of Factor 1

	Raw_alpha std.alpha G6(smc) average_r	S/N	ase	mean	SD
	0.84	0.84	0.84	0.27	5.4	0.01	0.13	0.19

Table 3

 3 Reliability of Factor 2

	Raw_alpha Std.alpha G6(smc) Average_r S\N	ase	mean	SD
	0.78	0.78	0.77	0.29	3.6	0.015	0.33	0.28


Jérôme Darmont

Le Gruenwald
email: gruenwal@mailhost.ecn.uoknor.edu

Blaise Pascal

Clustering Algorithms for Object-Oriented Databases

Keywords: Cactis, CK, Clustering, Object-Oriented Databases, ORION, Simulation

des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

INTRODUCTION

There are several ways to improve response time (i.e., to limit the number of disk Input/Output) in a DBMS. Indexing, clustering (i.e., storing related entities close together on secondary storage) and buffering (i.e., fetching clustered entities at the same time and setting up replacement strategies) are widely used techniques in conventional DBMSs. However, OODBs present additional semantics like structural properties (inheritance, composite objects) and interrelationships between objects. New techniques have then to be thought of.

We have chosen to study three clustering algorithms found in the literature that we consider to be different enough to be representative of the current research on clustering techniques in OODBs: Cactis, CK and ORION clustering algorithms. The Cactis and ORION clustering algorithms are already implemented in DBMSs.

These particular algorithms have been selected because they present characteristics that are interesting to compare. For instance, CK and ORION are dynamic clustering algorithms as the Cactis clustering algorithm is static. ORION also uses only users' hints to cluster a database; the Cactis clustering algorithm uses only statistics about the database and the CK algorithm makes use of both.

Furthermore, the aim of previous performance evaluations performed on these algorithms was only to compare the effects of one particular clustering strategy to those of a "no clustering" policy [START_REF] Chang | Effective Clustering and Buffering in an Object-Oriented DBMS[END_REF]HURS89]. We intend to compare each of these three algorithms to each other to determine which one performs the best in a given environment. The characteristics that make this algorithm the best should be isolated.

This paper is organized as follows. Section 2 explains the principles of clustering in OODBs. The three studied clustering algorithms are described in Section 3. Section 4 describes our simulation model. In Section 5, the simulation results are analyzed. Section 6 concludes this paper and provides future research directions.

CLUSTERING IN OODBs

Clustering principles

The goal of object clustering is to reduce the number of disk I/Os for object retrieval. Typically, the unit of data transferred from disk is a page instead of an individual object. If two objects are clustered on the same page, it will take only one disk I/O to access both objects successively. [START_REF] Hurson | Object-Oriented Database Management Systems: Evolution and Performance Issues[END_REF] Clustering algorithms attempt to improve the performance of object-oriented database systems by placing on the same page related sets of objects [START_REF] Tsangaris | On the Performance of Object Clustering Techniques[END_REF]. In object-oriented databases, complex objects are the basic units of data manipulation. The subobjects of a complex object may come from different classes. Traditional storage systems tend to group records of the same type physically close to each other on disk. This results in tedious and expensive reconstruction procedures (such as join operations) to retrieve complex objects. Therefore, it is logical to cluster related objects of different classes together to achieve acceptable performance. [START_REF] Hurson | Object-Oriented Database Management Systems: Evolution and Performance Issues[END_REF] The problem of clustering can be seen as a graph partitioning problem. The nodes of the graph are the objects and the edges are the links between objects. This problem is NP-complete. However, as the graph of objects represents the database state, all is needed is an incremental solution where new objects are placed at the "right place". Most of the algorithms used can be classified as greedy algorithms: they scan the objects according to their links and try to place them into the same cluster unit. Thus the cost of clustering has no major impact on the overall system.

[BENZ90]

Clustering strategies

According to [START_REF] Cattell | Object Data Management: Object-Oriented and Extended Relational Database Systems[END_REF], clustering in an OODB can actually be performed in many different ways:

• composite objects: objects can be clustered according to aggregation relationships;

• references: some OODBs allow objects to be clustered according to relationships with other objects; composite objects clustering is, in fact, a special case of this, clustered by aggregation relationships;

• object types: objects may also be clustered by their types; if there is a generalization hierarchy, subtype instances may also be clustered in the same segment;

• indexes: as in relational DBMSs, it may be possible to cluster objects by an index on their attributes;

• custom: some OODBs allow clustering to be performed "on the fly".

Unless objects are stored redundantly, an object can generally be clustered according to one of these rules. Where the rules do not conflict, however, it is possible to follow multiple clustering rules.

Clustering may be performed at two levels:

• pages: objects may be clustered according to the smallest physical unit read from disk, which is normally a page; this type of clustering can produce the greatest gains in performance when a "working set" of objects cannot be precisely defined for all applications; page clustering is more useful for clustering by index, reference and composite objects;

• segments: objects may be clustered in larger units, when the user is able to specify a meaningful logical grouping for segmentation; segment clustering is most useful for type clustering; it may also be used for composite objects, if used at a sufficiently course grain.

The largest performance gains are generally afforded by page clustering, since pages are the unit of access from disk and a "working set" of pages is selected dynamically according to the access characteristics of an application program. Segment clustering produces efficiency gains only if relatively large contiguous units are transferred from disk, or when efficiency gains can be made through grouping operations (for example, for composite objects deletion).

Users' hints

To expedite the retrieval of related data, database systems often take hints from the user (or database administrator) to store related data physically close together [START_REF] Kim | Object-Oriented Databases: Definition and Research Directions[END_REF]. For example, the GemStone database administrator, or a savvy application programmer can hint GemStone that certain objects are often used together and so should be clustered on disk [MAIE86]. The VBASE system allows explicit clustering hints when objects are created [START_REF] Andrews | Programming with Vbase[END_REF]. The strategy adopted in ONTOS is to allow the programmer to specify clustering and to provide tools for reclustering when more experience with the applications permits better choices to be made [START_REF] Andrews | ONTOS: A Persistent Database for C++[END_REF].

Static versus dynamic clustering

In the static case, clustering is done at the time objects are created and no reorganization is implied when the links between objects are updated [START_REF] Benzaken | Enhancing Performance in a Persistent Object Store: Clustering Strategies in O 2[END_REF]. A static clustering scheme offers a good placement policy for complex objects but does not take into account the dynamic evolution of objects. In applications such as design databases, objects are constantly updated during early parts of the design cycle. Frequent updates may destroy the initially clustered structure. To keep the object structure optimized, reorganization might be necessary for efficient future accesses [START_REF] Deux | The Story of O 2[END_REF].

Dynamic clustering is done at run time when objects are accessed concurrently and becomes attractive in an environment where the read operations dominate the write operations [START_REF] Benzaken | Enhancing Performance in a Persistent Object Store: Clustering Strategies in O 2[END_REF]. A dynamic clustering scheme should try to recluster when scattered access cost becomes too high. However, reclustering will generate overhead such as extra disk I/Os, so it is important to determine when a reorganization should occur. If the overhead is not justified, reclustering may actually degrade the overall performance [START_REF] Cheng | Effective clustering of complex objects in object-oriented databases[END_REF].

CLUSTERING ALGORITHMS

Cactis clustering algorithm

Cactis [START_REF] Hudson | Cactis: A Self-Adaptive Concurrent Implementation of an Object-Oriented Database Management System[END_REF] is an object-oriented, multi-user DBMS developed at the University of Colorado. It is designed to support applications that require rich data modeling capabilities and the ability to specify functionally-defined data.

The Cactis clustering algorithm is designed to place objects that are frequently referenced together into the same block (i.e., page, i.e., I/O unit) on secondary storage. It can improve response time up to 60%.

In order to improve the locality of data references, data is clustered on the basis of usage patterns. A count of the total number of times each object in the database is accessed is kept, as well as the number of times each relationship between objects in the process of attribute evaluation or marking out-of-date is crossed. Then, the database is periodically reorganized on the basis of this information. The database is packed into blocks using the greedy algorithm shown in Figure 1.

This clustering algorithm is also implemented in the Zeitgeist system [START_REF] Ford | ZEITGEIST: Database Support for Object-Oriented Programming[END_REF].

The Cactis clustering algorithm is a static algorithm since it is periodically used to recluster the database when the database is idle. This implies that the database is not clustered on the first run because no information about the database is available [START_REF] Chabridon | Clustering Techniques for Object-Oriented Database Systems[END_REF].

This algorithm does not require users' hints. This is an advantage since no arbitrary choice has to be made by the user [START_REF] Chabridon | Clustering Techniques for Object-Oriented Database Systems[END_REF]. But it also implies some time overhead (time to compute total number of times each object is accessed and number of times each relationship is crossed) and space overhead (the main memory space used to store the counters grows with the database size). It also raises the problem of getting pertinent statistics about the database.

Repeat

Choose the most referenced object in the database that has not yet been assigned a block. Place this object into a new block.

Repeat

Choose the relationship belonging to some object assigned to the block such that:

(1) the relationship is connected to an unassigned object outside the block and, (2) the total usage count for the relationship is the highest. Assign the object attached to this relationship to the block. Until the block is full. Until all objects are assigned blocks.

ORION clustering method

ORION is a series of next-generation database systems that have been prototyped at MCC (Microelectronics Computer Technology Corp.) as vehicles for research into the next-generation database architecture and into the integration of programming languages and databases [START_REF] Kim | Architecture of the ORION Next-Generation Database System[END_REF]. ORION has been designed for Artificial Intelligence (AI), Computer-Aided Design and Manufacturing (CAD/CAM) and Office Information System (IOS) applications [START_REF] Banerjee | Data Model Issues for Object-Oriented Applications[END_REF].

ORION supports only a simple clustering scheme. Instances of the same class are clustered in the same physical segment (i.e., a number of blocks or pages). Each class is associated with one single segment. [START_REF] Kim | Architecture of the ORION Next-Generation Database System[END_REF] But ORION also provides direct support for composite objects, i.e., objects with a hierarchy of exclusive component objects (see Figure 2). The hierarchy of classes to which the objects belong is a composite object hierarchy. The object-oriented data model, in its conventional form, is sufficient to represent a collection of related objects. However, it does not capture the IS-PART-OF relationship between objects; one object simply references, but does not own, other objects. A composite object hierarchy captures the IS-PART-OF relationship between a parent class and its component classes, whereas a class hierarchy represents the IS-A relationship between a superclass and its subclasses. [START_REF] Banerjee | Data Model Issues for Object-Oriented Applications[END_REF] Then it becomes advantageous to store instances of multiple classes in the same segment. User assistance is required to determine which classes should share the segment. The user can dynamically issue a Cluster message containing a "ListOfClassNames" argument specifying the classes that are to be placed in the same segment. [START_REF] Banerjee | Data Model Issues for Object-Oriented Applications[END_REF] In ORION, segments have a fixed size. So the number of pages they contain gives the number of I/Os necessary to load the segment. When a segment is full, a new page is allocated and linked to the segment (a pointer must be maintained in the segment descriptor). This -4 -implies some overhead to find the address of each additional page [START_REF] Chabridon | Clustering Techniques for Object-Oriented Database Systems[END_REF].

Figure 2: Example of composite object

The advantage of this method is its simplicity that makes the method fast and easy to implement since no cost model is defined and no overhead is implied to determine what is the optimal storage unit for an object. But simplicity also turns to a limitation since users' hints can only be based on the static information given by the data model and not on some information determined by the database usage and which could lead to a better clustering. [START_REF] Chabridon | Clustering Techniques for Object-Oriented Database Systems[END_REF]

CK clustering algorithm

The CK algorithm (from its authors' names: Chang and Katz) is defined in the CAD/CAM context. It can improve response time up to 200% when the Read/Write ratio is high (which is true for real CAD applications) [START_REF] Chang | Exploiting Inheritance and Structure Semantics for Effective Clustering and Buffering in an Object-Oriented DBMS[END_REF]. The CK algorithm makes use of several new concepts, such as structural relationships and instance-to-instance inheritance. Coupling the concept of versions with composite objects leads to configurations. A configuration is a composite unit whose components are bound to specific versions (see Figure 3) [START_REF] Chang | Inheritance in computer-aided design databases: semantics and implementation issues[END_REF].

Structural relationships

If two objects are alternative representations of the same real world entity, they are equivalent.

-5 -

Instance-to-instance inheritance

Besides structural relationships, inheritance provides additional semantics. As in object-oriented programming languages, a class/subclass hierarchy can be defined for an OODB based on the IS-A relationship. A subclass inherits the structure (i.e., attributes' definitions) and the methods of its superclass. However, in OODBs, this form of inheritance (called type inheritance) is not sufficient. [START_REF] Chabridon | Clustering Techniques for Object-Oriented Database Systems[END_REF] The CK algorithm also uses instance-to-instance inheritance that not only transfers the existence of attributes from one object to another (like type inheritance), but moreover the values of these attributes [START_REF] Wilkes | Instance Inheritance Mechanisms for Object Oriented Databases[END_REF].

Instance-to-instance inheritance is important in computer-aided design databases, since a new version tends to resemble its immediate ancestor. It is useful if a new version can inherit its attributes' values, and more importantly its constraints, from its ancestor.

[KATZ91]

Algorithm presentation

Instance-to-instance inheritance introduces more complexity because it allows attributes to be selectively inherited at run-time. This run-time flexibility requires a sophisticated approach for clustering. The CK algorithm is based on interobjects access frequencies (given by the user at data type creation time) for each kind of structural relationship, e.g., 20% of access along version relationships, 75% of access along configuration relationships and 5% of access along equivalence relationships.

When a new object is created, the algorithm chooses an initial placement based on which relationship is most frequently used to reach the object (in the above example, a new instance would probably be placed in the same page as its composite objects). Then, for each inherited attribute, cost formulas are used to choose between implementation by copy or by reference, i.e., either by copying the attribute's value or reference it with a pointer. The augmented access frequencies (i.e., relationship traversal frequencies plus inheritance traversal frequencies) may change the initial placement. The clustering algorithm pseudo code is given in Figure 4.

Then, if the best candidate page is full, either the next best candidate page is chosen or the page is split if the expected access cost resulting from the split is an improvement over placement in the next best candidate page.

Page splitting is performed by a greedy algorithm that partitions the inheritance-dependency graph into two sub-graphs that each fit into one page. This algorithm is not optimal, but it is linear (whereas an exact partitioning algorithm would be NP-complete). It is described in Figure 5.

SIMULATION MODEL

Object base

For our simulations, we used a random object base whose class hierarchy forms a DAG, as in [START_REF] He | An Efficient Storage Protocol for Distributed Object-Oriented Databases[END_REF]. The database generation was performed in two phases: first generate class hierarchies and class definition (see Figure 6), then generate instances for these classes. To simplify the class hierarchy, we did not take into account multiple inheritance because it has no effect on clustering. We also assumed that a given class had one single ancestor version and one single descendant version but could have several component classes or equivalent classes.

Instance creation has been designed as a special kind of query. However, the initial database is to be created before any other query can occur, given an initial number of objects. The method we used to generate instances is shown in Figure 7.

Query generation

The HyperModel Benchmark [START_REF] Anderson | The HyperModel Benchmark[END_REF][START_REF] Berre | The HyperModel Benchmark for Evaluating Object-Oriented Databases[END_REF] provides 20 different types of transactions. From those 20, we have isolated 15 types of transactions (some of them are slightly modified to match the structural relationships we use). Each transaction has a probability to occur.

• Name Lookup: Retrieve a randomly selected object; fetch one of its (randomly selected) attributes' value.

• Range Lookup: Select a class at random; select one of its attributes at random; determine randomly two test values; fetch all the attributes of all the instances of the class whose selected attribute's value are in the range defined by the test values.

• Group Lookup: Given a randomly selected starting object, fetch all the attributes of either:

-all its component objects, -all its equivalent objects, -all its descendant versions. • Reference Lookup: Given a randomly selected starting object, fetch all the attributes of either:

-its composite object, -all its ancestor versions. The Page_split algorithm assumes that the arc costs C ei (i.e., run-time lookup cost) between objects are always maintained and sorted. The node capacity Cap vi (i.e., the object size) is also maintained. Subset A and B represent the sets of objects assigned to the new pages after splitting. Both subsets are empty ate the beginning. E is the initial set of arcs relating the objects.

• Step (1): Select the maximum value arc from E as e target and set E to be (E -{e target }). Let v head and v tail be the head and the tail nodes of e target . • Step (2): Supposed both v head and v tail are new to subsets A and B. Insert v head and v tail in subset A if Cap vhead plus Cap vtail is less than the remaining capacity of subset A. Otherwise, insert v head and v tail in subset B if subset B has space for these nodes. If neither subset A or B could accommodate both v head and v tail , a broken arc is found and C etarget is added into C total .

• Step (3): Supposed v head is in subset A and v tail is not in subset A or B. Insert v tail into subset A if feasible. Otherwise, a broken arc is found and C etarget is added into C total .

• Step (4): Supposed both v head and v tail are visited before, a broken arc is found and C etarget is added into C total .

• Step (5): Look back to step (1) until arc set E is empty. Given a number of classes, we first build a class hierarchy that includes versions (1). Then we build a composite hierarchy and add equivalence relationships (2).

(1)

A new class is added.

A random number of versions of this class is added (descendant versions).

If the new class has a superclass (given a probability of having a superclass) then randomly select a superclass among the existing classes, inherit attributes and methods of the superclass, for each additional version of the class: randomly select a superclass among the initial class superclass descendant versions, inherit attributes and methods of the superclass. Add additional random attributes and methods to all versions (sizes of attributes and methods are assigned randomly). Compute object size for these classes. • Closure Traversal: Given a randomly selected starting object, follow one of the three structural relationships (i.e., version, configuration or equivalence) to a certain predefined (random) depth D; fetch a random attribute from the resulting object; the followed relationship can be either always the same or randomly selected.

• Editing: Select an object at random; update one of its attribute (randomly chosen) with a random value.

• Object Creation: Creation of a new object (cf. object base generation). This activates the CK clustering algorithm.

• Reclustering: The ORION clustering algorithm needs a "Cluster message" to be dynamically activated [START_REF] Banerjee | Data Model Issues for Object-Oriented Applications[END_REF]. The Cactis clustering algorithm is static. We can assume it will also wait for a cluster message before reorganizing the database. However, cluster messages for the Cactis algorithm should be far less frequent than cluster messages for the ORION algorithm since the Cactis clustering algorithm is supposed to run when the database is idle [START_REF] Hudson | Cactis: A Self-Adaptive Concurrent Implementation of an Object-Oriented Database Management System[END_REF].

Overall model

The overall simulation model is inspired by the one provided in [START_REF] Chang | Effective Clustering and Buffering in an Object-Oriented DBMS[END_REF]. It is composed as follows (see Figure 8). • Client module: After a predefined think time, the client issues the transactions to the Transaction Manager according to some frequencies of occurence.

• Transaction Manager module: The transaction manager extracts from transactions which objects have to be accessed or updated, and performs the operations. In the case of a regular operation, object requests are sent to the Buffering Manager. In the case of instance creation or a Cluster message, the Clustering Manager is invoked.

• Buffering Manager: The Buffering Manager checks if an object is in main memory and requests it to the I/O Subsystem if it is not. It also deals with page replacement strategie (when a new page is needed, the oldest page in memory is dropped and replaced by the new one).

• Clustering Manager: The Clustering Manager is activated depending on the algorithm (i.e., Cactis, CK or ORION) it implements. It deals with reorganizing the database on secondary storage to achieve better performance.

• I/O Subsystem: This module deals with physical accesses to secondary storage.

Simulation parameters

Tables 1 and 2 provide the simulation parameters we used for our simulation experiments.

SIMULATION RESULTS

To compare the performance of the three clustering algorithms, we conducted four testing cases: varying the database size, the workload, the buffer capacity and the Read/Write ratio. Due to space limitation, we present in the following subsections only some of the results we obtained.

Effects of the database size

We first tested the effect of varying the initial number of objects in the database using a uniform random distribution to choose the transactions' starting objects. This is not always realistic since there may be objects that are "hotter" (i.e., more frequently accessed) than others in real world applications. Furthermore, the performance of the Cactis clustering algorithm depends on run-time computed statistics, such as object's access frequencies, that are not the same when using different random distributions to select the transactions starting object. So we implemented in a second series of simulations a normal random distribution for the transactions' starting objects, which is very similar to the "skewed random" function introduced in [START_REF] Tsangaris | On the Performance of Object Clustering Techniques[END_REF].

Figure 9a shows that response time when using Cactis is 24 % lower than when using ORION. Figure 9b shows that, for CK, response time increases linearly with the number of objects and that CK algorithm totally outperforms the other two (being about 800 times better than Cactis). "PS ON" and "PS OFF" stand for page splitting used or not. The more a clustering algorithm is complex (i.e., the more it clusters object according to precise rules), the more it uses a greater amount of disk pages to cluster the object base. The maximum number of disk pages used (as shown in Figure 11), as expected, is higher for the more complex algorithms, i.e., CK needs 1.8 times as many pages as Cactis and Cactis needs 1.3 times as many pages as ORION, for which number of pages increases linearly.

Parameter name

Effect of the buffer capacity

On one hand, increasing the buffer capacity may lessen the effects of clustering since a given set of related objects has a higher probability of being in main memory instead of on secondary storage. On the other hand, objects are also accessed when reorganizing the database. Thus, increasing buffer capacity should decrease clustering overhead, especially for the ORION clustering algorithm that may make several non-consecutive accesses to each object. We performed this set of simulations using an initial database of 400 objects and selecting the transactions' starting objects from a uniform random distribution.

Figures 12a and12b show that response time decrease linearly with the buffer size for the Cactis and CK algorithms. The dual effect of increasing the buffer capacity is seen on both transactions I/Os and clustering overhead. The ORION algorithm has a similar behavior, but the gain in performance is seen earlier than with the other algorithms and then the gain in performance is less important (see Figure 12a). We can explain this by the fact that the ORION algorithm uses a smaller amount of pages than the other algorithms to cluster the database. Thus, the buffer size grows faster relatively to the database size. For instance, a buffer size of 20 pages represents 25% of the database size for ORION versus only 15% for Cactis and 9% for CK. Figure 12a presents rather big variations in performance when buffer capacity grows over 40 pages. However, these values oscillate around a mean value that decreases slowly but linearly.

Figure 12a: Response time vs. buffer size

Effect of the Read/Write ratio

Read/Write ratio is an important factor when seeking to evaluate DBMSs performances. Furthermore, [START_REF] Chang | Effective Clustering and Buffering in an Object-Oriented DBMS[END_REF] claims that CK algorithm performs better when the Read/Write ratio is high. For our simulation experiments, we used an initial database of 400 objects and a buffer size of 10 pages.

Figure 12b: Response time vs. buffer size

The performance of the Cactis and ORION algorithms decreases when the Read/Write ratio decreases (see Figure 13a). On the contrary, response time decreases along with the Read/Write ratio in the case of CK (see Figure 13b).

CONCLUSIONS

It is clear from our simulation experiments that the CK algorithm outperforms both Cactis and ORION in terms of overall performance. The results we obtained showed that this is due to both a good clustering capability and to the dynamic conception of the algorithm that allow an extremely low clustering overhead. Such a good behavior is achieved because the CK algorithm is activated only at object creation time and only accesses the few objects that are related to the newly created object once. Therefore, transactions are never blocked very long during clustering, as they are when the Cactis or the ORION algorithm is used. (The Cactis and ORION algorithms have to access all the objects in the database, even several times in the case of ORION, to reorganize the database; and transactions cannot be run when a reorganization occurs.) CK good clustering capability is based on the users' hints that specify the inter-objects access frequencies for each structural relationship and thus allows to cluster together objects that are likable to be accessed together.

Our simulations showed too that Cactis had also a good clustering capability. This is due to the use of statistics (i.e., objects access frequencies and relationships use frequencies) that allow to cluster together objects that are actually accessed together. Though, the Cactis algorithm is still completely outperformed by the CK algorithm. This is because, when using Cactis, clustering overhead increases very quickly with the number of objects, thus annihilating any gain achieved from good clustering capability. However, we have to keep in mind that this algorithm has been designed to run when the database is idle so that reclustering does not alter the database performance. Hence, if clustering overhead was not taken into account, the Cactis algorithm should perform about as well as CK algorithm as long as the statistics used during the last reorganization are pertinent.

In terms of disk space, the more a clustering algorithm is simple, the less space it should use. Actually, the more a clustering algorithm is complex, the more it clusters objects according to sharp criteria. Thus, a smaller number of objects are likely to be clustered in the same clustering unit (either a page or a segment). So the number of pages needed to store the database is greater. Our simulation experiments confirm that fact. The ORION algorithm is the less greedy algorithm in terms of disk pages used. Then the Cactis algorithm follows, using almost half the number of disk pages needed by CK to cluster the database. However, reorganizing the database, the Cactis and ORION algorithms need to build a new set of pages before deleting the old one. Thus they require about twice as much space as our graphs show.

Future research about this subject could be in a first step completing the simulation tests, notably by determining the effects of database changes, e.g., varying the probability for a class to belong to a composite class hierarchy, the average number and size of attributes, etc.

Then the next step would be the design and evaluation of one or several new clustering algorithms. One alternative would be to build a dynamic clustering algorithm that would use the same statistics as Cactis (i.e., objects access frequencies and relationships use frequencies) to cluster objects together, but could be able to use them at run-time (e.g., an algorithm activated at object creation time, like CK). Such an algorithm could have Cactis' good clustering capability without being handicapped by an important clustering overhead.

Another alternative would be to modify the CK algorithm so that it does not use users' hints for interobjects access frequencies any more and rely only on statistics, in order to make the algorithm even more accurate and performant. The problem with users' hints is that their accuracy depends the user (either the database administrator or a programmer) knowledge of the database. On the other hand, automatically gathered statistics show an exact image of the database status. Thus, by computing interobjects access frequencies for each structural relationship and each object at run-time, a better performance should be achieved.

Figure 1 :

 1 Figure 1: Cactis clustering algorithm [HUDS89]

  and equivalence relationships. Objects sharing the same interface but having different implementations are called versions [BATO85]. They represent different design alternatives. For example, if an object is identified by the pattern: Name[Version].Type where "Name" is the object name, "Version" its version number and "Type" its type; Nice[1].car, Nice[2].car and Nice[3].car would be three versions of the same object "Nice" type of which is "car".

Figure 3 :

 3 Figure 3: Example of configurations A very important characteristic of OODBs is the presence of composite (complex or nested) objects. This concept is represented through composite/component relationships among objects.Coupling the concept of versions with composite objects leads to configurations. A configuration is a composite unit whose components are bound to specific versions (see Figure3)[START_REF] Chang | Inheritance in computer-aided design databases: semantics and implementation issues[END_REF].If two objects are alternative representations of the same real world entity, they are equivalent.

Figure 4 :

 4 Figure 4: Pseudo code for CK clustering algorithm [CHAN90]

Figure 5 :

 5 Figure 5: Page_split algorithm [CHAN90]

  Scan all the classes. For each class: If it is a component of one class (given a probability of being component) then randomly select a class composed of the new class. If it has an equivalent class (given a probability of having an equivalent) then randomly select an equivalent class.

Figure 6 :

 6 Figure 6: Class lattice generation For each new object: Randomly select a class. If the new object class is a component of another class then randomly select an instance of this class (if any) to be composed of the new object. If the new object class is a version then randomly select one ancestor object in the new object class ancestor class, If using CK, inherit values of common attributes (either by copy or by reference). If the new object class has an equivalent class then randomly select one equivalent object among instances of the equivalent class.

Figure 7 :

 7 Figure 7: Instances generation

Figure 8 :

 8 Figure 8: Overall simulation model

Figure 9a :

 9a Figure 9a: Response time vs. number of objects (U) Figures 9a and 10 show indeed that Cactis performs 1.5 times better when objects are not accessed through a uniform distribution,

Figure 9b :

 9b Figure 9b: Response time vs. number of objects (U)

Figure 11 :

 11 Figure 11: Number of pages vs. number of objects

Figure 13a :

 13a Figure 13a: Response time vs. R/W ratio

•

  Sequential Scan: Select a class at random; select one of its attributes at random; fetch this attribute's values for every instance of the class.

	PROCEDURE cluster_object(target_objet)
	BEGIN
	/* step 1: get initial information */
	cluster_policy:=get_policy( );	/* Is page splitting enabled? */
	copy_set:=get_by_copy_set( );	/* Inherited attributes implemented by copy. */
	ref_set:=get_by_ref_set( );	/* Inherited attributes implemented by reference. */
	inh_page_set:=get_all_inh_page( );	/* Source pages for inherited attributes. */
	struct_page_set:=get_all_struct_page( );	/* Source pages for structural objects. */
	page_set:=inh_page_set+struct_page_set;
	/* step 2: calculate ref_set lookup cost for each page */
	FOR p IN page_set	/* If by-reference attribute r is */
		FOR r IN ref_set	/* not in page p, storing target object */
		IF r NOT_IN p	/* in page p requires one run-time */
		BEGIN	/* lookup for attribute r. */
		weight(p):=1/(prob(p,struct_rel));
		Ref_LookUp(p):=Ref_LookUp(p)+weight(p);
		END;
	/* step 3: calculate copy_set lookup and storage cost for each page */
	FOR c IN copy_set	/* If by-copy attribute c is not in page */
		FOR p IN page_set	/* p, we could either cache it in page p */
		IF c NOT_IN p	/* or change its implementation to be */
		BEGIN	/* by-reference. */
		weight(p):=1/(prob(p,struct_rel));
		Copy_storage(p):=Copy_storage(p)+size_of(c);
		Copy_LookUp(p):=Copy_LookUp(p)+weight(p);
		END;
	/* step 4: calculate total cost of every page. If by-copy attributes are */
	/*	implemented by reference, the total cost of storing target object */
	/*	in page p is represented by Total(p,1). Otherwise, the cost */
	/*	is represented by Total(p,2). */
	FOR p IN page_set
		Total_cost(p,1):=Ref_LookUp(p)*Lookup_cost+Copy_LookUp(p)*Lookup_cost;
		Total_cost(p,2):=Ref_LookUp(p)*Lookup_cost+Copy_storage(p)*Storage_cost;
	/* step 5: pick up best candidate page and try to insert the object */
	candidate_page:=Minimum(Total_cost);
	IF (cluster_policy EQ no_split)
		WHILE (NOT_FIT(candidate_page))
		candidate_page:=Next_Min(Total_cost);
	IF ((cluster_policy EQ page_split) AND (NOT_FIT(candidate_page))
		Split_page(candidate_page);
	END;

Table 1 :

 1 Static parameters

		Designation	Value	Justification, References
	RAVGTHINK	Average client think time	4 s	[CHAN89a]
	RCC	Average locking/unlocking	0.5 ms	[SRIN91]
		time (concurrency control)
	IMLVL	Multiprogramming level	10	[GRUE91]
	IWDSIZE	Size of one memory word	4 bytes	[GRUE91]
	ICPU	CPU power	2 Mips	[GRUE91]
	RMACC	Memory word access time	0.0001 ms	[GRUE91]
	RMTEST	Time for comparison of two	0.0007 ms	Two memory accesses, one
		memory words		subtraction
	IPGSIZE	Size of disk page	2048 bytes	[CHEN91]
	RSEEK	Average disk seek time	28 ms	[CHEN91]
	RLATENCY	Average disk latency time	8,33 ms	[CHEN91]
	RTRANSFER	Disk page transfer time	1.28 ms	[CHEN91]
	Parameter name	Designation	Default value	Range
	NCL	Number of classes	20	10-30
	IAVGVER	Average number of versions	3	1-5
		per class
	RPSUPER	Probability for a class of	0.9	0-1
		having a superclass
	RPCOMP	Probability for a class of	0.5	0-1
		being a component class
	RPEQUI	Probability for a class of	0.1	0-1
		having an equivalent class
	INOBJ	Initial number of objects	400	100-1000
	IAVGASIZE	Average attribute size	1 word	1-3 words
	IAVGNATTR	Average number of attributes	10	5-20
		per class
	IBUFF	Size of memory buffer	10 pages	10-100 pages
	IMD	Maximum depth in Closure	5	3-10
		Traversals
	ISEGSIZE	Default segment size	5	3-10
		(ORION)
	ITHRESHOLD	Update Threshold (CK)	25	0-255
	ISCALEF	Scale factor (CK)	0.5	0-1
	ISPLIT	Page split policy (CK)	ON	ON/OFF
	PT1-PT12	Probability of Read	0.065	0-1
		Transaction (#1-12)
	PT13	Probability of Editing	0.1695 (Cactis)	0-1
			0.169 (ORION)
			0.17 (CK)
	PT14	Probability of Object	0.05	0-1
		Creation
	PT15	Probability of Reclustering	0.0005 (Cactis)	0-1
			0.001 (ORION)
			0 (CK)
		Table 2: Dynamic parameters


Martin Kumm
email: kumm@uni-kassel.de

Oscar Gustafsson
email: oscar.gustafsson@liu.se

Florent De Dinechin
email: florent.de-dinechin@insa-lyon.fr

Johannes Kappauf
email: johannes.kappauf@student.uni-kassel.de

Peter Zipf
email: zipf@uni-kassel.de

Karatsuba with Rectangular Multipliers for FPGAs

de niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

I. INTRODUCTION

Karatsuba's method [START_REF] Karatsuba | Multiplication of multidigit numbers on automata[END_REF] was the first method for computing products with sub-quadratic complexity. It trades multiplications for additions, which are cheaper. It will be exposed in detail in Section II. In its original formulation, Karatsuba's algorithm is only expressed in terms of square multipliers, i.e., multipliers whose two inputs have the same number of digits. However, the multiplier resources available in recent Xilinx FPGAs are not square: they typically consist of a 18×25-bit signed multiplier which can be used for 17×24bit unsigned multiplication [START_REF]UltraScale Architecture DSP Slice User Guide (v1.6), Xilinx Corporation[END_REF]. The Karatsuba method is therefore inefficient on such FPGAs [START_REF] De Dinechin | Large Multipliers with Fewer DSP Blocks[END_REF], [START_REF] Pasca | High-performance floating-point computing on reconfigurable circuits[END_REF]: to apply it, one either needs to under-use the DSP blocks (use them as 17×17-bit multipliers), or complement them with (slower) logic to turn them into 24×24-bit multipliers. The first option is preferred, as it can exploit the optional pre-adder and postadder/accumulator that surround the multiplier in a DSP block [START_REF] De Dinechin | Large Multipliers with Fewer DSP Blocks[END_REF], [START_REF] Pasca | High-performance floating-point computing on reconfigurable circuits[END_REF].

This article attempts to reconcile Karatsuba's method with FPGA hardware whose DSP blocks are rectangular. It first slightly generalizes the classical Karatsuba formulation. It then shows how rectangular multipliers can be used under certain constraints on their aspect ratio.

This problem corresponds to sparse polynomial multiplication, so the suggested algorithms also find use here. Previous work in this area primarily focus on asymptotically efficient results or comparisons for polynomials with a random sparseness [START_REF] Malaschonok | Fast multiplication and sparse structures[END_REF], [START_REF] Van Der Hoeven | On the bit-complexity of sparse polynomial and series multiplication[END_REF]. In [START_REF] Van Der Hoeven | On the bit-complexity of sparse polynomial and series multiplication[END_REF], the authors mention regarding Karatsuba's method for sparse polynomial multiplication: "In the sparse case this phenomenon hardly occurs, and it is commonly admitted that this approach is useless". The current work shows that there are use cases, at least when the sparseness is regular, and that significant savings can be obtained compared to a straightforward evaluation. The authors are not aware of any explicit results for multiplication of sparse polynomials with a regular sparseness.

Back to FPGAs, the proposed technique is able to save a smaller proportion of the multipliers compared to classical Karatsuba using only square multipliers. However, since each rectangular multiplier is used almost to its full potential, the proposed technique saves resources and improves latency for large multipliers (above 64×64 bits). This is confirmed by actual synthesis results on recent Xilinx devices. Very large integer multipliers could be an important component for the booming field of fully homomorphic encryption (see for instance multipliers from 944×944 up to 2560×2560 bits in [START_REF] Moore | Targeting FPGA DSP slices for a large integer multiplier for integer based FHE[END_REF]).

II. CLASSICAL KARATSUBA METHOD

A. Two-Part Splitting

Consider a large multiplication of size 2W × 2W bits. It can be split into smaller multiplications of size W × W each by splitting the arguments into smaller segments of size W , leading to

A × B = (a 1 2 W + a 0 )(b 1 2 W + b 0 ) (1) = a 1 b 1 =M4 2 2W + (a 1 b 0 =M3 + a 0 b 1 =M2 )2 W + a 0 b 0 =M1 . (2)
The basic idea of Karatsuba's algorithm is based on the identity:

a 1 b 0 + a 0 b 1 = (a 0 + a 1 )(b 0 + b 1 ) -a 0 b 0 =M1 -a 1 b 1 =M4 (3)
Hence, by reusing the sub-products M1 and M4, we can compute the sum of M2 and M3 by a single multiplication: this reduces the number of smaller multiplications from four to three. The price to pay are two new additions computing a 0 + a 1 and b 0 + b 1 (called pre-additions in the following), and two additional negative terms in the final sum (called postadditions). Besides, the new product is a (W +1)×(W +1)-bit one, hence requires a slightly larger multiplier than each of the W × W -bit products it replaces.

Karatsuba's technique has been used in software for fast multiple-precision arithmetic. Equation ( 2) is applied recursively, and the recursion typically stops when the smaller multipliers match the capabilities of the hardware multipliers offered by the processor.

The present work addresses the design of large multipliers for FPGAs [START_REF] De Dinechin | Large Multipliers with Fewer DSP Blocks[END_REF], [START_REF] Pasca | High-performance floating-point computing on reconfigurable circuits[END_REF], [START_REF] Gao | Asymmetric large size multipliers with optimised FPGA resource utilisation[END_REF], [START_REF] Kumm | Optimal design of large multipliers for FPGAs[END_REF]. It is closer to hardware multiplier design [START_REF] Ercegovac | Digital Arithmetic[END_REF], [START_REF] Jaiswal | VLSI Implementation of Double-Precision Floating-Point Multiplier Using Karatsuba Technique[END_REF]: the relevant metrics here are area and delay. Area-wise, Karatsuba reduces the cost for large enough values of W . Exactly how large is technology-dependent, and we will only address here FPGA technology with embedded hard multipliers.

Delay-wise, post-additions may be performed in constant time using carry-save arithmetic. Equivalently, they can be merged with negligible overhead in the final bit array compression. Pre-additions, on the other hand, have a significant timing overhead due to the need for carry propagation. Therefore, Karatsuba will typically improve area, but degrade timing.

An alternative form of (2) is

a 1 b 0 + a 0 b 1 = (a 1 -a 0 )(b 1 -b 0 ) + M 1 + M 4 . ( 4
)
It uses pre-subtractions, which have the same hardware cost as pre-additions. However, the product is now a product of signed numbers. This will therefore be the preferred formulation on FPGAs, whose DSP blocks are capable of signed multiplication. The extra bit added by the pre-subtractions is now a sign bit, allowing us to exploit the sign bit inputs of the DSP blocks that would otherwise be wasted.

B. Terminology and Graphical Representation

Throughout this article, we will use a tile-based graphical representation introduced in [START_REF] Pasca | High-performance floating-point computing on reconfigurable circuits[END_REF]. For instance, Fig. 1 illustrates the representation of (2). A multiplication is represented as a rectangle. Decomposing the inputs A and B into subwords splits this rectangle with vertical and horizontal lines respectively. Each of the sub-products appears as a smaller rectangle called a tile throughout this article. Fig. 1(a) shows square tiles, while Fig. 4 shows multiplications decomposed in rectangular tiles. When two multipliers are paired by Karatsuba, they are linked on the figure (Fig. 1(b)). Such a link means that the sum of the two linked tiles will be computed by a single multiplication, reusing the sub-products corresponding to tiles with black squares. The size of this multiplication is 1-bit larger than the tile size in both dimensions (and more if Karatsuba is applied recursively).

C. Square K-Part Splitting

The inputs to a large multiplication may also be split into K segments of W bits [START_REF] Montgomery | Five, six, and seven-term Karatsuba-like formulae[END_REF]:

A × B = K-1 i=0 2 iW a i K-1 j=0 2 jW b j (5) = i,j 2 (i+j)W a i b j (6)
In [START_REF] Van Der Hoeven | On the bit-complexity of sparse polynomial and series multiplication[END_REF], any expression a i b j + a j b i may be replaced as follows:

a i b j + a j b i = (a i + a j )(b j + b i ) -a j b j -a i b i (7)
which again computes the sum of two tile subproducts using only one multiplier. The novelty is that subproducts may be reused more than one time, which further improves the efficiency of the method. Take for example, a 3W × 3W multiplier where the arguments are split into three parts

A × B =(a 2 2 2W + a 1 2 W + a 0 )(b 2 2 2W + b 1 2 W + b 0 ) (8) =a 0 b 0 + (a 0 b 1 + a 1 b 0 )2 W + (a 0 b 2 + a 2 b 0 + a 1 b 1 )2 2W + (a 1 b 2 + a 2 b 1 )2 3W + a 2 b 2 2 4W (9)
=a 0 b 0 + ((a 0 + a 1 )(b 0 + b 1 ) -a 0 b 0 -a 1 b 1 )2 W + ((a 0 + a 2 )(b 0 + b 2 ) -a 0 b 0 -a 2 b 2 + a 1 b 1 )2 2W + ((a 1 + a 2 )(b 1 + b 2 ) -a 1 b 1 -a 2 b 2 )2 3W + a 2 b 2 2 4W . (10)
Here, (7) could be used three times, which reduces the multiplier count from 3 × 3 = 9 to only six. The K-Part splitting is a straightforward application of rule (7) on as many partial products as possible. Figure 2 shows examples of 4-part, 6-part and 7-part splitting.

In general, K-Part splitting saves a triangle of K(K -1)/2 multiplications. For instance, in the 4-part splitting of a 4W × 4W multiplier shown on Fig. 2(a), six of the 16 required W × W bit multiplications can be saved. This corresponds to the number of tile pairs on the figure.

D. Recursive Karatsuba

The multiplication schemes above can also be applied recursively (it was actually the original formulation [START_REF] Karatsuba | Multiplication of multidigit numbers on automata[END_REF]), i.e., each multiplier is split into smaller multiplications where each of the smaller multiplication is itself split into smaller multiplications, etc.

Consider the 4W × 4W multiplication again. It can be realized by using three multiplications of up to (2W + 1) × (2W + 1) using the 2-part splitting in [START_REF]UltraScale Architecture DSP Slice User Guide (v1.6), Xilinx Corporation[END_REF]. Each of these (2W + 1) × (2W + 1) multiplications can then be realized by using three (W + 1) × (W + 1) multiplications by applying Fig. 2: Tilings using the conventional Karatsuba with square 17 × 17 bit multipliers another 2-part splitting. This leads to a total of only nine (W + 1) × (W + 1) multiplications (compared to ten in the 4-part splitting). However, this comes at the price of additional critical path delay or latency, as two pre-additions have to be performed in sequence.

In other words, in hardware, the choice between K-part splitting or its recursive application exposes a trade-off between latency and number of multipliers.

III. KARATSUBA WITH RECTANGULAR MULTIPLIERS

A. Generalized Square Karatsuba Karatsuba works by pairing two multipliers a i b j and a j b i which have the same weight 2 w in the sum defining the large multiplication. On a tiling representation such as Figure 2, this means they are aligned on a NW-SE diagonal.

A first observation is that the pattern that results from Karatsuba can be arbitrary shifted on the rectangle. In other words it is possible to pair any tile that share the same weight: as soon as i + j = k + = s, the complete product involves 2 sW (a i b j + a k b ), and it is therefore possible to use the rewriting

a i b j + a k b = (a i + a k )(b j + b ) -a i b -a k b j (11)
or

a i b j + a k b = (a i -a k )(b j -b ) + a i b + a k b j ( 12
)
assuming a i b and a k b j are already computed. Note that these formulae generalize [START_REF] Moore | Targeting FPGA DSP slices for a large integer multiplier for integer based FHE[END_REF] and ( 4). Graphically, this can be viewed as applying Karatsuba on a sub-square of the large multiplier. This generalization is in general less interesting than the classical K-part decomposition, because the latter exposes more reuse of the diagonal subproducts. However it could be used to apply Karatsuba technique to non-square large multipliers: rectangular ones, or truncated multipliers, for instance.

This generalization is also key to understanding how the Karatsuba technique can reuse rectangular sub-products.

B. Weight-aligning Rectangular Tiles

In order to use [START_REF] Jaiswal | VLSI Implementation of Double-Precision Floating-Point Multiplier Using Karatsuba Technique[END_REF] or [START_REF] Montgomery | Five, six, and seven-term Karatsuba-like formulae[END_REF] when the products are rectangular ones, they need to have the same binary weight. The trick is therefore to find splittings of the two inputs that expose such alignment.

Consider the splitting of argument A in W A -bit chunks, and argument B into W B -bit ones. The weight of a i b j is now 2 W A i+W B j . Therefore, for a i b j and a k b to share the same weight, we must have

W A i + W B j = W A k + W B for i = k and j = .
We can rewrite this as

W A N -W B M = 0 with N, M ∈ N . (13)
Now, the smallest values of N and M to satisfy [START_REF] Brent | Modern Computer Arithmetic[END_REF] are obtained by M = W A /W and N = W B /W where W is the greatest common divisor (GCD) of W A and W B , i.e.,

W = gcd(W A , W B ) .
Hence, the first common weight that appears is 2 W N M . Thus, the smallest multiplier for which Karatsuba can be applied is of size W M (N + 1) × W N (M + 1).

For example, consider a tile exactly matching the Xilinx DSP block in unsigned mode: W A = 17 and W B = 24. As W A and W B are relatively prime, we have W = 1, M = 17 and N = 24. Relation (13) can only be satisfied for N being multiples of 24 and M being multiples of 17, which is only useful for very large multipliers starting from 17 • (24 + 1) × 24 • (17 + 1) = 425 × 432 bits.

However, if we accept to use the slightly smaller tile size 16 × 24 (which means under-using the DSP blocks, but much less than if we use them as 17 × 17), then we get a much larger GCD W = gcd(16, 24) = 8, with M = 16/8 = 2 and N = 24/8 = 3. The minimum large multiplier for which we may apply Karatsuba is now 8

•2•(3+1)×8•3•(2+1) = 64×72.
This specific example is shown in Fig. 3(a). On this figure, we made the choice that the index of each A chunks is 2i, and the index of each B chunk is 3j, which makes it easier to spot the situations where 2i + 3j = 2k + 3 .

Before we further look into specific implementation issues, we will first analyze different large multiplier sizes and their corresponding amount of small multipliers by using their polynomial representation.

IV. POLYNOMIAL INTERPRETATION

Fast multiplication algorithms are often described as polynomial multiplication [START_REF] Montgomery | Five, six, and seven-term Karatsuba-like formulae[END_REF], [START_REF] Brent | Modern Computer Arithmetic[END_REF]. For instance (8) can be read as the product of two polynomials in the variable x = 2 W . The product of polynomials of similar orders corresponds to large multipliers that are approximately square. Let us consider a few potentially useful cases.

A large multiplier of size W (N + 1)M × W (M + 1)N corresponds to the following polynomial multiplication of an N + 1-term M -sparse polynomial by an M + 1-term N -sparse polynomial, both in x = 2 W :

  N j=0 a M j x M j   M k=0 b N k x N k = 2M N i=0 c i x i . ( 14
)
For example, a large multiplier of size 8W × 9W , constructed from 2W × 3W tiles, can be expressed as

a 0 + a 2 x 2 + a 4 x 4 + a 6 x 6 b 0 + b 3 x 3 + b 6 x 6 = 12 i=0 c i x i . (15)
The advantage of this representation is that we can identify the left-hand side and the right-hand side of [START_REF] Ugurdag | Hardware division by small integer constants[END_REF], which provides the values of the polynomial coefficients:

c 0 = a 0 b 0 c 1 = 0 c 2 = a 2 b 0 c 3 = a 0 b 3 c 4 = a 4 b 0 c 5 = a 2 b 3 c 6 = a 0 b 6 + a 6 b 0 c 7 = a 4 b 3 c 8 = a 2 b 6 c 9 = a 6 b 3 c 10 = a 4 b 6 c 11 = 0 c 12 = a 6 b 6 (16)
which shows where Karatsuba can be applied: one multiplier can be saved for c 6 on this example, with the Karatsuba identity a 0 b 6 + a 6 b 0 = (a 0 -a 6 ) (b 0 -b 6 ) + c 0 + c 12 . This product requires eleven multipliers instead of twelve for the direct evaluation. The polynomial point of view also tells us that this is the optimal value, since there are eleven non-zero c i coefficients.

In general, such an algorithm can be derived that requires M N + M + N multipliers, which is one less compared to the direct evaluation.

Another case is constructing a large multiplier of size 2W N M × 2W M N . Here, the polynomial multiplication can be written as

  2N -1 j=0 a M j x M j   2M -1 k=0 b N k x N k = A 0 (x) + A 1 (x)x M N B 0 (x) + B 1 (x)x M N , (17)
where

A 0 (x) = N -1 j=0 a M j x M j A 1 (x) = 2N -1 j=N a M j x M j-M N B 0 (x) = M -1 k=0 b N k x N k B 1 (x) = 2M -1 k=M b N k x N k-M N . ( 18
)
Using a polynomial version of ( 2), ( 17) can be expressed using only three polynomial multiplications, each of which requires M N multiplier tiles, so in total 3M N instead of 4M N multiplier tiles. The last considered case is a large multiplier of size W (2N + 1)M × W (2M + 1)N . This can be written similar to [START_REF] Brunie | Arithmetic core generation using bit heaps[END_REF], but with

A 1 (x) = 2N j=N a M j x M j-M N B 1 (x) = 2M k=M b N k b N k-M N , (19)
i.e., one more term in each of the A 1 (x) and B 1 (x) polynomials. Now, again, three polynomial multiplications can be computed based on [START_REF]UltraScale Architecture DSP Slice User Guide (v1.6), Xilinx Corporation[END_REF]. The multiplication A 0 (x)B 0 (x) requires M N multipliers as above. However, for (A 0 (x) + A 1 (x)) (B 0 (x) + B 1 (x)) and A 1 (x)B 1 (x), it is now possible to use the approach for W (N + 1)M × W (M +1)N multipliers leading to M N +M +N multipliers.

Besides, the product a 2M N b 2M N appears in both polynomial multiplications, and, hence, only must be computed once. In total, a W (2N + 1)M × W (2M + 1)N multiplication require 3M N + 2M + 2N -1 rectangular multipliers instead of 4M N + 2M + 2N + 1 for direct evaluation. More complexity results for rectangular multipliers are summarized in Table I. The lower bounds are based on the number of non-zero coefficients in the resulting polynomial. It should be noted that the lower bounds can always be obtained, but sometimes the pre-and post-computation will become more complex. See, e.g., three-term multiplication with five square multipliers [START_REF] Bodrato | Integer and polynomial multiplication: Towards optimal toom-cook matrices[END_REF]. It requires division by three, but this operation is quite cheap on FPGAs [START_REF] Ugurdag | Hardware division by small integer constants[END_REF]. This remains to be studied in detail.

N M × M N M N - M N b (N + 1)M × (M + 1)N M N + M + N + 1 M N + M + N M N + M + N c 2N M × 2M N 4M N 3M N 3M N d (2N + 1)M × (2M + 1)N 4M N + 2M + 2N + 1 3M N + 2M + 2N -1 3M N + M + N

V. DESIGN OF CONCRETE MULTIPLIERS

In the following, we consider the design of concrete multipliers targeting recent Xilinx FPGAs with DSP blocks providing a 18 × 25 signed multiplication.

A. Discussion on Other Possible Rectangular Tilings

A natural question to answer is: are there other possibilities of rectangular tilings like the 16 × 24 tiling discussed in Section III-B that would lend themselves to Karatsuba pairing?

We considered the following tiles:

• 18 × 24 (with one line of the multiplication performed using logic resources). This leads to W = gcd(18, 24) = 6, M = 3 and N = 4. • 15×25 (under-using the DSP in one dimension, and again with one line of the multiplication performed using logic resources). This leads to W = 5, M = 3 and N = 5.

Figure 3 shows the smallest possible multipliers on which Karatsuba can be applied with these tiles. A detailed comparison of the resulting number of small multipliers when using one of the different options for M , N and W and the cases of Table I is given in Table II, sorted by the resulting large multiplier size. We conclude that Karatsuba opportunities are higher for the 16 × 24 configuration, and select this tile for actual evaluation in the rest of this work.

Besides, this configuration is also the simplest one to use as each tile uses just one DSP block without additional logic. As the result from the pre-addition grows in word size by one bit, it would require a 17×25 (unsigned) multiplication. However, it is simple to circumvent this by selecting the alternative form given in [START_REF] Montgomery | Five, six, and seven-term Karatsuba-like formulae[END_REF], which leads to subtractions in the pre-processing. The multiplier is now 17 × 25 signed, and this fits very well the 18 × 25 signed multiplier available in the DSP block.

B. Results on Concrete Multipliers

We designed several multipliers using the classical Karatsuba using square tiles, the conventional tiling (without any reduction) using rectangular tiles as well as the proposed Karatsuba method using rectangular tiles. The size of the square tiles was selected to be 17 × 17 and the rectangular tiles was selected to be 16 × 24 as discussed above. The sizes of the large multipliers were selected to be as close to each other as possible to achieve a direct comparison. The resulting tilings are shown in Fig. 4 and their concrete coefficients c i are given in appendix. Table III compares the operation counts in terms of their used amount of small multipliers, pre-adders and post-adders for all three methods.

The proposed Karatsuba method using rectangular tiles requires the least multipliers except in the 68 × 68 case, where classic Karatsuba uses one small multiplier less.

In terms of adders, the proposed method also significantly improves the numbers of pre-and post-adders. The main reason for this is of course the larger tile size, which leads to fewer sub-products, hence pre-adders.

Note that for the larger multipliers using the proposed method, many of the pre-adders can be shared as they compute the same values. For the 96×96, only 5 out of 12 pre-additions compute different values. For the 112 × 120 multipliers, only 7 pre-additions are required out of 16 (see appendix). For the traditional Karatsuba, no sharing is possible as each preaddition only appears once.

VI. SYNTHESIS RESULTS

Table III shows the expected trade-off between multipliers and adders used for pre-and post-processing. To be able to compare the actual performance and resource consumption (including pipeline resources etc.), we designed a VHDL code generator for the multipliers using the different methods [START_REF] De Dinechin | Custom arithmetic datapath design for FPGAs using the FloPoCo core generator[END_REF]. FloPoCo also provides a stateof-the-art framework to create and optimize compressor trees [START_REF] Brunie | Arithmetic core generation using bit heaps[END_REF], [START_REF] Kumm | Advanced compressor tree synthesis for FPGAs[END_REF]. It was used to implement all the post-adders within a single compressor tree. For each Karatsuba sub-product, one of the pre-adders was implemented using the pre-adder within the DSP block, while the other was implemented using logic. This further reduces about half of the pre-adders of Table III that are not shared.

Table IV shows synthesis results on Xilinx Virtex-6 using ISE. Results for Kintex-7 using Vivado are similar. As expected from Table III, the tiling approach typically requires the least logic resources in terms of look-up tables (LUTs) but the most DSP resources. Using the conventional Karatsuba with square multipliers helps reducing the DSP count but at the cost of a highly increased LUT count: more than 50% compared to the tiling approach. The proposed rectangular Karatsuba reduces the DSP count compared to the tiling approach with only a slight increase in logic resources. As a consequence, the latency (number of cycles) is also reduced.

VII. CONCLUSION AND FUTURE WORK

In this work, an extension of Karatsuba's method was presented that exploits rectangular-shaped multipliers. Necessary conditions were derived showing that Karatsuba's method can be applied when the word lengths of the two inputs of these multipliers have a large GCD. Different large multipliers were designed for the general case, showing the benefits of the proposed extension compared to the conventional tiling. Based on that, several concrete multipliers were implemented for recent Xilinx FPGAs providing 18×25-bit signed multipliers in their DSP blocks. With this technique, a significant reduction in arithmetic operations (multipliers and adders) is possible. Synthesis experiments showed that this also predictively translates to a reduction of DSP blocks and logic resources.

The proposed technique is probably not useful when targeting ASIC or software, although it could find applications in the multiplication of polynomials with very specific sparseness properties.

Future work will be directed towards the further exploration of possible large multiplier sizes, and exploring more formulae [START_REF] Montgomery | Five, six, and seven-term Karatsuba-like formulae[END_REF]. Another goal is a fully automated design flow that selects the best fitting tile, integrated in a generic multiplier optimization framework [START_REF] De Dinechin | Large Multipliers with Fewer DSP Blocks[END_REF], [START_REF] Kumm | Optimal design of large multipliers for FPGAs[END_REF].

Fig. 1 :

 1 Fig. 1: Graphical tiling representation of (2)

  68 × 68 (4W × 4W , W = 17) 102 × 102 (6W × 6W , W = 17) 119 × 119 (7W × 7W , W = 17)

Fig. 3 :

 3 Fig. 3: Minimal Karatsuba patterns with various rectangular tiles matching Xilinx DSP blocks.

  64 × 72 (8W × 9W , W = 8) 96 × 96 (12W × 12W , W = 8) 112 × 120 (14W × 15W , W = 8), see Appendix C

Fig. 4 :

 4 Fig.4: Rectangular Karatsuba tilings selected for synthesis. They mostly use 16 × 24 tiles, replicating the pattern of Fig.3(a)

TABLE I :

 I Number of rectangular W M × W N tiles for different multiplier sizes. N, M relative prime.

				Number of tiles of size W M × W N
	Case	Large multiplier size (×W )	Tiling	Karatsuba	Lower bound
	a

TABLE II :

 II Karatsuba cases for M and N when mapped to Xilinx DSP blocks M N W Tile size Case Large mult. size Small mult.

	2	3	8	16 × 24	b	64 × 72	11
	3	4	6	18 × 24	b	90 × 96	19
	2	3	8	16 × 24	c	96 × 96	18
	3	5	5	15 × 25	b	90 × 100	23
	2	3	8	16 × 24	d	112 × 120	27
	3	4	6	18 × 24	c	132 × 132	36
	3	5	5	15 × 25	c	150 × 150	45
	3	4	6	18 × 24	d	160 × 168	49
	3	5	5	15 × 25	d	165 × 175	60
	17 24 1	17 × 24	b	425 × 432	449

TABLE III :

 III Operation counts for similar multiplier sizes

		Square				Rectangular
		Karatsuba			Tiling		Karatsuba
	Size	Mult Pre-	Post-	Size	Mult =	Mult Pre-	Post-
			add	add		Post-add		add	add
	51 × 51	6	6	6	48 × 48	6	6	0	6
	68 × 68	10	12	22	64 × 72	12	11	2	13
	102 × 102 21	30	51	96 × 96	24	18	5	30
	119 × 119 28	42	70	112 × 120 35	27	7	43

TABLE IV :

 IV Actual synthesis results obtained for Virtex 6 FPGA (xc6vlx760-ff1760) using Xilinx ISE 13.4, post place&route

			Square							Rectangular
			Karatsuba					Tiling				Karatsuba
	Size	DSPs LUTs Cycles fmax [MHz]	Size	DSPs LUTs Cycles fmax [MHz] DPSs LUTs Cycles fmax [MHz]
	68 × 68	10	1405	11	215.1	64 × 72	12	764	10	217.5	11	867	10	247.0
	102 × 102	21	2524	13	192.0	96 × 96	24	1586	13	215.1	18	2032	14	195.1
	119 × 119	28	3438	15	192.6	112 × 120	35	2293	16	218.9	27	2292	14	190.1

APPENDIX

A. Coefficients for 8W × 9W = 64 × 72