19th ICCRTS

Title of Paper: Enhancing Information Awareness Through Directed Qualification
of Semantic Relevancy Scoring Operations

Assigned Paper #: 027

Primary Topic: Data, Information and Knowledge

Alternatives: Organizational Concepts and Approaches; Experimentation,
Metrics, and Analysis

Authors:

Jason Bryant, Greg Hasseler, Matthew Paulini, Timothy Lebo

Organization:

Air Force Research Laboratory

RISA - Information Management Technologies

525 Brooks Road

Rome, NY 13440

Point of Contact: Jason Bryant

Organization Phone: (315)330-7670

Organization Email<EMAIL_ADDRESS>
Distribution A: Approved for public release; distribution is unlimited.

(Approval AFRL PA #88ABW-2014-1863)

# Enhancing Information Awareness Through Directed Qualification of Semantic
Relevancy Scoring Operations

Jason Bryant, Greg Hasseler, Matthew Paulini, Timothy Lebo  Air Force Research
Laboratory - RISA Information Management Technologies
Distribution A: Approved for public release; distribution is unlimited.
(Approval AFRL PA #88ABW-2014-1863)

###### Abstract

Successfully managing analytics-based semantic relationships and their
provenance enables determinations of document importance and priority,
furthering capabilities for machine-based relevancy scoring operations.
Semantic technologies are well suited for modeling explicit and fully
qualified relationships but struggle with modeling relationships that are
qualified in nature, or resultant from applied analytics. Our work seeks to
implement the autonomous Directed Qualification of analytic-based
relationships by pairing the Prov-O Ontology (W3C Recommendation) with a
relevancy ontology supporting analytics terminology. This work results in the
capability for any semantically referenced document, concept, or named graph
to be associated with the results of applied analytics as Direct Qualification
(DQ) modeled relational nodes. This new capability will enable role, identity,
or any other content-based measures of relevancy and analytics-based metrics
for semantically described documents.

##  I Introduction

Robustly supporting mission solutions within a C2 information domain is
difficult when mission information needs cannot be satisfied with currently
available information, fluctuate, or if there are unforeseen state changes for
mission circumstances. C2 Agility defines how to flexibly support operations
within a single C2 space, as well as how and when to appropriately transition
between C2 Approaches for a particular mission and its circumstances. Ideally,
maximizing agility would provide tailored solutions for adjusting to changes
that occur within the circumstances of the mission. In practice, however,
changing mission circumstances can be managed more simply through enhanced
mission modeling, while a lack of suitable information that assists the
deconfliction of prioritization-based mission states is more difficult to
solve.

The lack of suitable information, or which lack relevance measures for
determining suitability, is a relatively common challenge, yet is resist to
mission modeling solutions. Our approach seems to provide mission operations
with information that was previously non-existent, non-queryable, or
incorrectly deemed irrelevant. Advanced features of semantic mission modeling
can be used in concert with traditional approaches to increase agility in the
face of insufficient information. This results in meeting mission information
needs by increasing the quality of information available by determining
relevancy, and increasing the quantity of information through mission domain
semantics.

The primary focus of this effort is to enable new features for semantics-based
relevancy modeling and analytics. Semantic-based graphs traditionally only
support reasoning that is logic-based, whereas non-semantic knowledge graphs
are commonly evaluated using traversal queries, popularity, similarity,
clustering, or other analytics. Analytics-based graph analytics have never
been sufficiently modeled ontologically in order to enable being paired with
semantic inferencing engines. Direct Qualification (DQ) is the means by which
semantic modeling can be applied to express these probabilistic or analytics-
based relationships and bridge the current divide between semantic inferencing
logic and graph-based analytics.

In this paper, we show that Directed Qualification, introduced by the Prov-O
ontology, can be combined with a relevancy ontology for modeling analytical
evidence supporting semantic relationships while avoiding the pitfalls of
reification. This enables techniques used to evaluate non-semantic knowledge
graphs to be applied to semantic-based knowledge graphs. We demonstrate this
ability by applying the Betweenness, PageRank, and HITS analytics to a
semantic-based knowledge graph derived from an operational scenario.

While there are ongoing efforts towards document analysis using analytics such
as PageRank [1], VSM, HITS, etc., the focus of these efforts has been on
ontology matching [2] or temporal/geospatial query enhancement [3]. Our
approach differs in that it stays confined to semantic technologies. Enabling
analytic provenance relationships and the qualification of applied analytics
for interrelated documents provides critical capabilities for result set
relevancy scoring, however, some intrinsic difficulties within semantic
standards and technologies require mitigation.

In the following section, we discuss why the ability to model analytical
evidence in semantic-based knowledge graphs is valuable to Command and Control
(C2) environments. Section IV describes the technical work necessary to
implement directed qualification for modeling analytics. Section V describes
our experimental setup, while Section VI describes the results. Finally,
Section VII concludes our work and discusses potential applications and future
work.

##  II Background

A current complexity in C2 support is adequately defining the transition
requirements triggering a change in the C2 Approach for a set of entities or
collectives. The triggers are generally event-based from either information
publications within the mission’s C2 domain, or a set of entity interaction
pattern occurrences from across one or more C2 domains (e.g., Edge,
Conflicted, etc.). Our approach focuses on the evaluation and semantic
modeling of event-based information publications springing from mission
resources. We demonstrate how greater command and control agility is achieved
through pairing document-based semantic relevancy scoring and modeling with
graph-based analytics and traceability to persisted source documents.

Provenance for semantically represented documents provides support for
attribution of authorship, change tracking, sourcing, and any other transform
related to an entity, activity, or agent involved with the document. Our
research uses the Prov-O[REF] Ontology and direct qualification of semantic
relevancy scores to manage these relationships.

Semantic provenance for documents supports a slightly different subset of
features than semantic provenance for non-document-centric relationships. Non-
document-centric relationships lack the context of sourcing unless explicitly
and independently associated via provenance relationships. The consequent
semantically expressed relationships lack traceability.

Semantic provenance for documents is handled less explicitly by using the
unique document URI as the named graph, or quads, for all relationships
extracted from the document. This traceability is important because without
introspection into referential sourcing there is a limited measure of trust in
data content. For non-deterministic relationships, the implications of using
semantics grow even more complex. Many probabilistic analytics improve
reliability and trust when trends of an increasing or decreasing score are
tracked over time.

A key advantage of pairing provenance and relevancy vocabularies is the power
it provides to overcome the complexity of semantic reification. Reification,
an intrinsic complexity of the semantic standards, is the consequence of
attempting to simplify all relationships into Subject-Predicate-Object sets.
It is normally implemented when a semantically modeled instance is seeking to
express either the qualification or provenance of a relationship. These two
cases can be mitigated without resorting to reification, however. Adopting a
quad-based perspective of semantic relationships can achieve a basic form of
provenance by allowing traceability to the source named graph’s unique URI.
The Prov-O ontology expands the set of provenance support and supplies some
generalized predicates for qualification. This effectively solves the non-
probabilistic subset of analytics use cases. However, even with pairing both
of these approaches there is a failure to solve the qualification of
probabilistic analytics, such as the results of Vector Space Modeling,
PageRank, HITS, or other Natural Language Processing (NLP) analytics. Our
approach towards supplying these capabilities is the Direct Qualification of
probabilistic relationships with a supporting relevancy ontology.

The primary steps for enabling Direct Qualification are outlined below, and
described more completely in Sections IV, V, and VI.

  1. 1.

Support persistence for raw documents and semantic quad-based relationships,
ideally by using the semantic URI of the document’s named graph as the unique
key for the raw document retrieval.

  2. 2.

Strictly enforce the separation of the semantic models for class instances
from the events affecting their state relationships.

  3. 3.

Support graph-based processing of analytics over semantic edges and vertexes.

  4. 4.

Support event-based relevance scoring triggers, such as SPARQL queries, XPath
queries, semantic reasoning, or keyword searches of raw text.

  5. 5.

Determine the appropriate Direct Qualification Model based upon tests for
occurrence, continuance, and the monotonicity of the entities involved in the
applied analytic.

  6. 6.

Express the relevancy scoring of documents through the pairing of a provenance
ontology with a relevancy ontology.

  7. 7.

Persist the DQ results within the quad-store.

##  III Motivation And Related Work

Data can be looked at from multiple domain-agnostic viewpoints, although each
possesses intrinsic advantages and disadvantages. For example, the Internet
can be viewed as a series of interconnected documents, or, if all content were
to be extracted, as a set of interconnected facts, social networks, people,
geo-locations, media, and applications. While these views are not mutually
exclusive, applications are generally oriented towards a single paradigm. C2
environments share a great deal of similarities with these paradigms, even if
obscured by segmented tiers of access control, middleware management tools,
multiple security configurations, and mixed levels of resources for enterprise
and edge domains. From either perspective of the data, the environment can be
simplified to the information management of archived documents, document
publications, and content knowledge.

By embracing a data perspective that combines relationships for unstructured
knowledge representation with structured, document-centric relationships, the
process of determining, modeling, and expressing relevance with semantic
technologies can be performed. Our approach seeks to solve a combination of
challenges within Information Extraction (IE), Information Management (IM),
Semantic Information Modeling, Data to Information (D2I), and Quality of
Service (QoS) Enabled Dissemination (QED).

##  IV Modeling and Applying Directed Qualification for Analytics

Direct Qualification (DQ) for documents is the determination of their
relevancy, considered either in combination or in isolation, and the
appropriate semantic modeling of the results paired with the result of a
stochastic analytic. DQ enables query capabilities for both the analytic
results and the captured analytic qualification relationships for provenance.
To formalize the problem faced when attempting to perform DQ we first need to
explicitly define the concepts and steps involved. Primary concepts include
qualification, provenance, specialization, relevancy scoring, occurrent and
continuant state events, idempotent and non-idempotent analytics, and
monotonicity.

The qualification of a relationship is an expression of how two entities, or
in our case documents, are associated. For example, the foaf ontology supports
properties that can declare whether two people know each other, but does not
support the qualification of how, why, and to what degree they know each
other. They also do not capture probabilistic relationships, such as the
result of an analytic determining a strong likelihood that one person knows
another. DQ provides the discoverability and traceability of the analytic
qualification that resulted in the probabilistic relationship. Possible
relationship qualifications that could be applied to the knows property of the
foaf ontology are found in the Prov-O W3C Recommendation. The provided set of
qualifications are general enough to provide generic use case solutions, but
specific enough to extend with domain-based qualifiers if necessary. The
Prov-O ontology, currently a W3C recommendation, seeks to provide a set of
general provenance concepts and properties for interconnecting entities,
activities, and agents. As an example, some supported properties are
wasAttributedTo, wasAssociatedWith, used, wasGeneratedBy, actedOnBehalfOf, and
wasDerivedFrom. Our work extends the provenance properties to support the
expression of qualifications that are probabilistic in nature. We also extend
the Prov-O concepts of entity, activity, and agent to relevancy counterparts
such as idempotent, stochastic, or boolean analytics. These enhancements are
intended to support modeling of analytic qualifications and results
semantically.

Provenance supports relationship state changes, which have varying degrees of
complexity via specialization. Semantic technologies serve multiple knowledge
representation use cases, one being the expression of static relationships
(Occurrent), the other being the expression of stateful (Continuant)
relationships. Either one of these relationship types may be expressed
independently as an RDF triple or message and document dependent as an RDF
quad, using the source message / document as a possessive named graph. RDF and
OWL are ideally suited to stateless, independent facts, as long as trust
determinations, document traceability, and sourcing are non-critical features.
However, in most real world use cases these features become critical to
determining truth and relevancy. For example, if semantic relationships are
extracted from multiple sources that disagree on a date, identity, event,
target, mission, or other relevant fact, and these facts are expressed
utilizing solely triples, a determination of truth must be made on which
relationship is correct. Determining truth among conflicted relationships is
nearly impossible without first determining trust levels of the extraction
sources. Once a source becomes more trusted than another, a form of provenance
is pulled back into the process, whether implicitly or explicitly.

The type of relationships are also important to consider. Some attributes of
an asset may be occurrent (e.g., name, identity, asset type, etc.), while
others are continuant (e.g., fuel level, latitude, longitude, role, etc.).
Semantics, even when using instances of an entity, treat all relationships as
occurrent, although there is allowance for limiting their cardinality. OWL,
SPARQL, and most ontologies do not have a built in mechanism to support the
distinction between occurrent and continuant relationships. In order to
retrieve changes of state for a data or object attribute of an instance, that
attribute must be explicitly defined within an ontology or an additional,
customized layer of abstraction.

DQ and a relevancy ontology must support complex and diverse analytics
modeling. Some analytics result in outputs with probabilistic relational
implications, while others result in boolean results. Some analytics can be
aggregated into a normalized set, while others must be evaluated individually.
Some are idempotent, always resulting in the same value, regardless of whether
they were executed successively. A stochastic analytic results in a non-
deterministic value for the state of a relationships. For example, calculating
the VSM similarity of two documents may result in a particular keyword being
correlated by a value of 5.6. Is this important or relevant? It lacks much
value unless normalized or racked against a threshold acting as a heuristic
determination.

DQ required the construction of supporting infrastructure, including a quad-
store, a raw document storage DB, and a graph-based analytics framework. In
our experiments we used both Parliament and Virtuoso as quad-stores (wrapping
the Jena graph interface), flat files for raw document storage (referenced by
a key-value pair hash map), and Jung for graph-based analytics. Each document
is viewed concurrently as an independent publication and a semantic named
graph, while the query results are autonomously mapped from a semantic graph
result set to a traditional vertexes/edges graph tailored for analytics
scoring.

Following the establishment of the infrastructure, appropriate semantic models
for object instances need to be adopted, which supports semantic distinctions
from assets and their state, as well as provides state traceability queries.
Some semantic models adopt a constantly ”present” based view that updates the
instance of the mission, target, person, etc. with relationships reflecting
any changes in its state. This is unwise because the state change’s value can
never be considered truly distinct from its identity URI. Specialization
qualifications within the Prov-O ontology reduce relationship duplication
while creating the capabilities for more advanced analytics. Jung, an open-
source graph-based analytics framework, was extended to enable its built in
analytics over semantic graphs represented using the Jena framework
interfaces. Once the semantic and non-semantic graphs were made interoperable
we constructed an experimentation harness that performed sample SPARQL queries
and relevancy analytics over the test scenario. The initial set of analytics
applied included ”Betweenness,” ”PageRank,” and ”HITS.”

DQ may not be necessary for all cases where analytics provenance is desired.
Applicability can be determined by applying the test matrix in Figure 1 to a
possible use case. In the case where a semantic data or object relationship is
expressing an event that is occurrent and non-probabilistic in nature, DQ
modeling will not yield any new insights over traditional semantic inferencing
or reasoning. In the case where an entity-entity relationship is continuant,
or state-based, but non-probabilistic in nature, the specialization provenance
feature enables traceability for state management. DQ is applicable for all
analytics-based value outputs, although it is important to note that DQ is
implemented differently depending upon the nature of the event.

|  |  State Change Event
---|---|---
|  |  Continuant |  Occurrent
Relationship Type |  Analytic |  Specialization and Direct Qualification |  Direct Qualification
Attribute |  Specialization |  Default Semantic Inferencing and Reasoning

Figure 1: DQ Decision Matrix

ptPageRankAnalyticprov$:$Activityxsd:doublexsd:doublexsd:integerPageRankScoreprov$:$Entityxsd:doublexsd:dateTimeInformation
Aprov$:$Entityrelevancy:scoreprov:generatedAtTimeprov:wasGeneratedByrelevancy:tolerancerelevancy:alpharelevancy:maxIterationsprov:used
Figure 2: Simple Entity to Entity DQ Model ptVSM
Similarityprov$:$EntityCollectionprov$:$EntityInformation
Aprov$:$EntityInformation Bprov$:$EntityVSM
SimilarityAnalyticprov$:$Activityxsd:doublexsd:integerxsd:doublexsd:dateTimerelevancy:deviationprov:generatedAtTimeprov:wasGeneratedByrelevancy:querytermrelevancy:vectorweightprov:usedprov:usedprov:wasDerivedFromdcterms:hasPartdcterms:hasPart
Figure 3: Complex Entity to Entities DQ Model

Occurrent relationships present the simplest opportunity to apply DQ. They are
relatively simple to model, will never require adjustment, and have a common
form of expression regardless of tye type of analytic being applied. Figure 2
illustrates the application of the PageRank analytic to a document. The
PageRank analytic applied to semantic node graphs produces dynamically
adjusting normalized scores because the publication of subsequent documents
grows the degree of interconnections for the document. This should,
theoretically, predict an increased likelihood of popularity. This analytic
differs from others such as the Vector Space Modeling (VSM) estimation for a
single document. Regardless of subsequent published relationships VSM will
result in the same normalized values of keyword frequency. Even if VSM
estimates are aggregated for an entire collection of documents, the score will
not change based on alterations within the knowledge graph. These aggregate
document analytics, however, leave the monotonic realm of entity-to-entity DQ
models, and enters the realm of entity-to-entities DQ models.

There are two complex use cases for applying DQ. One use case is continuant
relationships that derive from applied analytics. The other use case is for
qualification relationships that are non-monotonic. Monotonicity can mean
different things depending on whether it is applied in mathematical functions,
logic, or semantics, but our use of the term describes the uni-directional,
single object capabilities that limit semantic relationships. Figure 3
illustrates a non-monotonic relationship applying DQ between multiple
documents. This is a complex case because DQ is being used as an alternative
to reification in qualifying an analytic to multiple sources or causes.
Applying DQ in these forms to analytics value results in the capability to
semantically express both the provenance, inputs, qualifications, and results
of analytics. Together these can validate the quality and relevance of the
information.

##  V Experiment Setup

The mission-based test scenario consisted of 230 messages published over a
period of 10 minutes. The message types included USMTF formatted ATOs, Intel
Reports, Battle Damage Assessments, Close Air Support Requests, F15, Predator,
and MRAP CoT Blue Force Tracking messages, and JTAC Red Force Tracking status
observations. The semantic relationships created were produced by means of the
extraction framework we created in our previous ICCRTS research [4], with
added support for GeoSPARQL location extractions.

Simulated mission data is published and semantically expressed via a set of
indexers/extractors. The result of semantic processing is a semantic document
represented via RDF/OWL relating internal values for details involving times,
locations, missions, targets, points of contact, etc. An example document from
a Blue Force Tracking extraction is shown in Listing 1.

Listing 1: Semantic Document Resulting From Semantically Processing a Blue
Force Track.

⬇

<http://phoenix.rl.af.mil/im.owl#Payload?id1ff6f625e02118959d2b54af2aff>

rdf:type im:Payload ;

im:formatId ”cot” ;

im:type ”a-f-A-M-F-Q-a” .

scenario:Pred1

im:publishedInformation

<http://phoenix.rl.af.mil/im.owl#Information?idd761961c4eb4918385775832c8a4> ;

im:hasLocation

<http://www.lanuv.nrw.de/osiris/geometries/adce33b2-24c6-469a-8aac-27860d51df0b>
;

im:publisherId ”Pred1” .

<http://phoenix.rl.af.mil/im.owl#Information?idd761961c4eb4918385775832c8a4>

rdf:type im:Information ;

im:hasPayload
<http://phoenix.rl.af.mil/im.owl#Payload?id1ff6f625e02118959d2b54af2aff> ;

im:hasPublisher scenario:Pred1 ;

im:informationType ”mil.af.rl.cot” .

im:involvesMission “247A” .

im:involvesAsset “Pred1” .

im:taskStart

[ rdf:type time:Instant ;

time:inDateTime

[ rdf:type time:DateTimeDescription ;

time:day ”—11”^^<http://www.w3.org/2001/XMLSchema#gDay> ;

time:hour ”19”^^<http://www.w3.org/2001/XMLSchema#nonNegativeInteger> ;

time:minute ”00”^^<http://www.w3.org/2001/XMLSchema#nonNegativeInteger> ;

time:month ”–02”^^<http://www.w3.org/2001/XMLSchema#gMonth> ;

time:timeZone ””^^<http://phoenix.rl.af.mil/&tz-world;ZTZ> ;

time:year ”2012”^^<http://www.w3.org/2001/XMLSchema#gYear>

]

] ;

<http://www.lanuv.nrw.de/osiris/geometries/adce33b2-24c6-469a-8aac-27860d51df0b>

<http://www.opengis.net/ont/geosparql#asWKT>
”<http://www.opengis.net/def/crs/OGC/1.3/CRS84> POINT (4.86035239692792
48.41661096320327)”^^<http://www.opengis.net/ont/sf#wktLiteral> .

Ontology support includes common solutions for time, geospatial (GeoSPARQL),
common elements (U-Core SL), and custom ontologies for mission planning,
information management, and relevancy. Format and XML type determination is
performed in a pre-processing stage prior to semantic extraction, if
applicable. The Aperture open source project was adopted to provide the
majority of the format and type determination solution, although customization
for DoD formats was required. After stages for pre-processing, format
determination, type determination, and semantic extraction completes, the
execution of the analytics and DQ are executed as part of the query process.

##  VI Relevancy

Representing the relevancy of documents measured via analytics that score
them, either independently or in concert with other documents, presents
multiple obstacles. The first challenge is within provenance modeling itself.
Modeling document relevancy should result in a cohesive solution that uses a
clean, simple, and straightforward query expression. Unfortunately, many of
the provenance-based qualification relationships apply to use cases where
entities, activities, or agents have been qualified either singularly or in
pairs, but not as a composite. This greatly increases the complexity of the
query expression. Secondly, the complexity of reification within semantic
technologies makes it difficult to express the results of an analytic
qualified relationship between entities with a cardinality of greater than
one. These issues can be overcome in various ways, some of which are described
below.

Analytics that can process a semantic graph and enable relevancy determination
must be applied selectively through best fit evaluations. For example, some
analytic frameworks, such as Google’s MapReduce or Natural Language Processing
(NLP), operate over raw documents upon either their publication or being
returned as a DB query result. These frameworks are tailored for document or
key/value pair stores such as Hadoop or Cassandra. Semantic inferencing can
create a form of analytics by applying an ontology relevant to the domain and
setting up type, sameness, and equivalence rules. For example, if an
extraction from two documents results in the determination that there are
matching identifiers for a mission, target, asset, or person, then the
respective attribute can be inferred to have “sameness,” an instance
equivalence. This is a common feature of establishing property chains within
OWL 2. Semantic reasoners support rule-logic that can determine if the value
of a relationship has reached a particular threshold, but do not support
features for analytics for graph traversal, analytics modeling, or state
change events, which is where our approach fills the gaps.

Relevancy determination can supply critical C2 features for both general and
tailored solutions for information quality, prioritization, and stochastic
relationship models. Some forms of relevancy can be compared to enhancing a
search engine. Documents found by keyword searches have long been ordered by
estimating relevance by applying some kind of popularity analytic. This has
generally remained unobtainable for semantic queries because the use cases
have either not been document-based or were unable to be processed by non
rule-logic analytics within semantic data sets.

Many web-oriented popularity, similarity, and clustering analytics appear to
be well suited for semantic datasets. Our framework adopted an initial set of
analytics for use, including PageRank, HITS, and Betweenness. These stochastic
solutions fit well as the nature of a document-oriented semantic dataset is
identical in many ways to the nature of the Internet itself. The Internet is
an HTML representation of multiple knowledge domains overlayed upon a set of
segmented documents (with unique URLs), while a document-oriented semantic
dataset is an RDF/OWL representation of multiple knowledge domains overlayed
upon a set of segmented named graphs (with unique URIs). Both datasets contain
interlinkings between documents, the only difference being that the links on
the Internet are not explicitly tied to a particular ontology.

Figure 4: Example Results of Applying Analytics with DQ

Our proof of concept for DQ seeks to apply relevancy analytics intended for
the world wide web for semantic analysis. Our rsearch does not validate the
quality of these analytics, but only seeks to model them appropriately via
semantics. PageRank attempts to determine relevancy based upon links between
webpages or semantic named graphs, using weight normalization to determine the
likelihood of being at the node while doing random graph traversals. HITS
seeks to determine the degree our named graphs are mutually reinforcing, and
which named graph documents are authorities (highly interconnected). The
output shown in Figure 4 is an example of DQ results for analytics applied to
semantic named graphs, illustrating multiple analytic values for a query
result set, and subsequently published to the semantic quad-store.

##  VII Conclusion

DQ models enable users to take advantage of multiple analytic paradigms and
increase the quantity and quality of information available to users and
administrators within a C2 domain. Semantic technologies can reap the benefits
of graph-based analytics, traditionally considered separate and distinct,
while allowing for the document-oriented nature of a traditional database and
its paired features. These capabilities are obtained without degrading the
semantic knowledge representation, but instead amplifies the capabilities so
that SPARQL queries could be paired with additional document-based analytics
available from other query languages and platforms.

Semantic modeling and persistence of the document DQ results enable some
groundbreaking and novel features that should be more fully explored. One
novel consequence is that SPARQL queries can order their semantic result set
of document associated named graphs according to a set of prescribed
analytics. For example, while keyword-based search analytics are commonly
implemented by Google and other search providers in a way that orders results
by a set of popularity and analytic oriented measures, semantic queries never
have. By constraining named graphs within the quad-store to act as document
references, DQ empowers the ORDER BY command within SPARQL to construct a
document result set graph that can sort results by any expressed, normalized
analytic score.

Another advantage of DQ is that analytic provenance and results can themselves
be inference and reasoned upon. This enables an additional level of
functionality that could reason a particular threshold value of an analytics
score has been reached, triggering additional relationships with impacts
affecting document prioritization, access control, security classification, or
quality assessment.

These enhancements enable determinations of efficiency for different
analytics, and have the potential to combine analytic-based queries with
semantic queries. Applying these models, ontologies and approaches to an
operational set of mission data can make that information, and its relevancy
score results, more discoverable and of higher quality.

## References

  * [1] C. Ding, X. He, P. Husbands, H. Zha, and H. D. Simon, “Pagerank, hits and a unified framework for link analysis,” in _Proceedings of the 25th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval_ , ser. SIGIR ’02. New York, NY, USA: ACM, 2002, pp. 353–354.
  * [2] R. Tous and J. Delgado, “A vector space model for semantic similarity calculation and owl ontology alignment,” in _Proceedings of the 17th International Conference on Database and Expert Systems Applications_ , ser. DEXA’06. Berlin, Heidelberg: Springer-Verlag, 2006, pp. 307–316.
  * [3] M. Perry, A. Sheth, I. B. Arpinar, F. Hakimpour, and H. A. Karimi, “Geospatial and temporal semantic analytics,” in _Handbook of Research on Geoinformatics_ , Hershey, PA, 2009, pp. 161–170.
  * [4] J. Bryant and M. Paulini, “Making semantic information work effectively for degraded environments,” in _Proceedings of the 18th International Command and Control Research and Technology Symposium_ , June 2013.
  * [5] N. R. T. Group, “Executive overview of c2 agility,” NATO Science and Technology Organization, Tech. Rep. STO-TR-SAS-085, November 2013.
  * [6] U. J. F. Command, “Command and control joint integrating concept,” Department of Defense, Tech. Rep., September 2005.
  * [7] T. Lebo, A. Graves, and D. L. McGuinness, “Contentpreserving graphics,” in _Proceedings of Consuming Linked Data Conference_ , 2013.
  * [8] R. Bunescu and R. J. Mooney, “Collective information extraction with relational markov networks,” in _Proceedings of the 42nd Annual Meeting on Association for Computational Linguistics_ , ser. ACL ’04. Stroudsburg, PA, USA: Association for Computational Linguistics, 2004.
  * [9] J. Bryant, V. Combs, J. Hanna, G. Hasseler, T. Krokowski, B. Lipa, J. Reilly, and S. Tucker, “Phoenix base implementation: Final technical report,” DTIC, Tech. Rep., 2010.
  * [10] J. Bryant, V. Combs, J. Hanna, G. Hasseler, R. Hillman, B. Lipa, J. Reilly, and C. Vincelette, “Phoenix: An abstract architecture for information management final technical report,” DTIC, Tech. Rep., 2010.
  * [11] L. A. Barroso, J. Dean, and U. Hölzle, “Web search for a planet: The google cluster architecture,” _IEEE Micro_ , vol. 23, no. 2, pp. 22–28, March 2003.
  * [12] A. Yakushiji, Y. Miyao, T. Ohta, Y. Tateisi, and J. Tsujii, “Automatic construction of predicate-argument structure patterns for biomedical information extraction,” in _Proceedings of the 2006 Conference on Empirical Methods in Natural Language Processing_ , ser. EMNLP ’06. Stroudsburg, PA, USA: Association for Computational Linguistics, 2006, pp. 284–292.
  * [13] K. Sudo, S. Sekine, and R. Grishman, “An improved extraction pattern representation model for automatic ie pattern acquisition,” in _Proceedings of the 41st Annual Meeting on Association for Computational Linguistics - Volume 1_ , ser. ACL ’03. Stroudsburg, PA, USA: Association for Computational Linguistics, 2003, pp. 224–231.
  * [14] J. R. Hobbs, D. Applet, J. Bear, D. Israel, M. Kameyama, M. Stickel, and M. Tyson, “Fastus: A cascaded finite-state transducer for extracting information from natural-language text,” in _Finite-State Language Processing_. MIT Press, 1997, pp. 383–406.
  * [15] M. Schrage, “The struggle to define agility,” _CIO Magazine_ , August 2004\.
  * [16] R. A. Shulstad, “Cursor on target: Inspiring innovation to revolutionize air force command and control,” _Air & Space Power Journal_, vol. XXV, no. 4, pp. 19–28, Winter 2011.


# An Energy-efficient Capacitive-Memristive Content Addressable Memory

Yihan Pan${}^{\textsuperscript{ \href https://orcid.org/0000-0002-2666-5540}}$
Adrian Wheeldon${}^{\textsuperscript{ \href
https://orcid.org/0000-0003-4672-5990}}$
Mohammed Mughal${}^{\textsuperscript{ \href
https://orcid.org/0000-0002-1061-6576}}$ Shady Agwa,
Themis Prodromakis${}^{\textsuperscript{ \href
https://orcid.org/0000-0002-6267-6909}}$ and Alexantrou
Serb${}^{\textsuperscript{ \href https://orcid.org/0000-0002-8034-2398}}$ Y.
Pan, A. Wheeldon, M. Mughal, S. Agwa, T. Prodromakis and A. Serb are with the
Centre for Electronics Frontiers, Institute for Integrated Micro and Nano
Systems, School of Engineering, University of Edinburgh, EH9 3LA, UK. (emails:
<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>aserb@ed.ac.uk).

###### Abstract

Content addressable memory is popular in the field of intelligent computing
systems with its searching nature. Emerging CAMs show a promising increase in
pixel density and a decrease in power consumption than pure CMOS solutions.
This article introduced an energy-efficient 3T1R1C TCAM cooperating with
capacitor dividers and RRAM devices. The RRAM as a storage element also acts
as a switch to the capacitor divider while searching for content. CAM cells
benefit from working parallel in an array structure. We implemented a 64 x 64
array and digital controllers to perform with an internal built-in clock
frequency of 875MHz. Both data searches and reads take 3x clock cycles. Its
worst average energy for data match is reported to be 1.71 fJ/bit-search and
the worst average energy for data miss is found with 4.69 fJ/bit-search. The
prototype is simulated and fabricated in 0.18 um technology with in-lab RRAM
post-processing. Such memory explores the charge domain searching mechanism
and can be applied to data centers that are power-hungry.

###### Index Terms:

Content addressable memory(CAM), capacitive-divider, resistive random-access
memory(RRAM)

##  I Introduction

Traditional memory structures such as SRAM and DRAM are address-addressable
only. With the development of intelligent systems, address-addressable-only
memories limit computing efficiency in terms of data processing and
transferring. Advanced intelligent systems require not only memory storage but
also the ability to locate memory addresses by certain content[1]. We call
this type of memory content addressable memory (CAM), also known as
associative memory. The search-by-content manner of CAMs enables data visible
to the system and accelerates information processes to focus on their location
of interests without other extra data movement compared to the von Neumann
architecture. Therefore, the ability of bit storage and comparison has made
CAM attractive to the field of network routers [2], packet classification [3],
neuromorphic computing [4], reconfigurable computing [5], pattern recognition
[6], and data compression [7].

Conventional CAM in CMOS technology normally uses SRAM as memory elements to
store data and its data comparison is implemented by NAND-based [8] or NOR-
based [9] topologies. A basic binary CAM typically has 10T (transistors)
whereas it also can be implemented into a ternary CAM that takes two SRAM
together to acquire an additional state called ‘don’t care’ in 16T [10]. CAM
cell allows parallel searching and they normally been built with memory
arrays. Studies have looked for a denser and more robust solution with less
power consumption in the SRAM-based design [11]. Although the CAM memory is
desired because of its high operational speed and searching function, its
density increases its cost of implementation more than the other standard
memories in CMOS. Thus, emerging memories beyond CMOS technologies have been
taken into the field to maintain a high throughput rate with a reduction in
area [1].

Emerging devices are treated as canonically non-volatile and their
characteristics depend on the properties of their fabrication materials or
structures. They are categorized by their operation mechanisms such as
Resistive Random Access Memory (RRAM) [12], Phase Change Memory (PCM) [13],
Ferroelectric RAM (FeRAM) [14], and magnetic RAM (MRAM) [15]. Those devices
have a common factor that they can be altered to different states leading to a
suitable technique for memory. As a result, the bit storage for CAM with
emerging technologies is achieved by the device itself instead of two SRAMs
(12T). At the same time, the bit comparison utilizes the differences between
states to distinguish the stored bit on the device. In this work, we are
focused on RRAM whose resistivity can be altered to different levels. The
Metal-Insulator-Metal (MIM) structure of RRAM changes its resistance by redox
processes, coupling to ion-migration effects [16]. In other words, the device
resistance can be switched to a low resistance state (LRS) or a high
resistance state (HRS) by applying set and reset threshold pulses
respectively. Some material structure also allows middle resistance states to
form the RRAM a multi-bit memory cell [17].

(a)

(b)

Figure 1: (a) Measured RRAM static IV characteristics at different resistance
levels. Resistance values in the legend are quoted in Ohms and for a read-out
voltage of 0.2V. (b) Pristine RRAM static IV comparison with its fit line at
218 k in the logarithmic domain. (positive direction).

Existing non-volatile CAMs are proposed with a much dense area. The RC-XNOR-Z
in [18] uses RRAM for storage and XNOR gate for evaluation. The non-volatile
device can be also used for evaluation such as the 4T2R RRAM-based TCAM
proposed in [19]. It implies an RC delay but suffers from a long recovery time
for high RRAM resistive states. The same group also researched a 3T1R TCAM
[20] further to improve the performance. However, the 3T1R solution works as a
resistor divider which has a direct current path, consuming a significant
portion of energy inefficiently, waiting for RC stabilization. Hewlett Packard
lab developed a 4T2R cell in 2019 [21] with improved energy efficiency but
longer search latency. IBM contributes to a 2T2R structure based on PCM [22]
with a 2-bit encoding scheme. The memory development in the charge domain is
also designed with FeFET in 2021 [23]. Analogue CAM has also been developed by
[24] where the multilevel of RRAM resistive states shows the possibility for
complex searches. Overall, the RRAM-based TCAM shows promising performance in
search delay and power among those different nvTCAMs [1]. It is essential to
find improved power efficiency solutions with a high throughput rate at low
cost and high reliability for CAM designs.

In this paper, we propose a capacitive-based RRAM CAM with energy-efficient
solutions operated with an 875 MHz clock. The pixel operates in the charge
domain with no direct current path. It offers both address addressable read
and content addressable search with lower energy consumption compared to the
state-of-the-art. In section II, we first introduce an RRAM model built based
on our own fabricated devices. Then, the pixel and system performance are
highlighted in section III. Section IV provides the analysis of the
experimental measurements and follows with further discussions and a
conclusion at the end.

##  II RRAM model

In this work, the in-house fabricated non-volatile RRAM with a structure of
Au/TiO2/Pt is applied to the CAM pixel. We model our RRAM devices based on the
modeling approach in [25], where we have modified the equations for the IV
characteristics as shown below. As in the original modeling work, device model
parameters are directly derived from measured static IV characteristics of
Au/TiO2/Pt devices [26] (i.e. it is a data-driven model), as shown in fig. 1.
Here, we assumed that the resistive states of the device do not change during
any read and search operations unless the devices are actively programmed. We
fit experimental IV data into the following exponential equation:

$i(v)=\begin{cases}a_{p}(1/RS)(1-exp(-b_{p}v))&v>0\\\
a_{n}(1/RS)(1-exp(-b_{n}v))&v<0\end{cases}$ (1)

where $a_{p,n}$ and $b_{p,n}$ are fitting parameters at the resistance RS. A
comparison example between a real device and its fitted model in fig. 1 proves
its accuracy. The exponential relation indicates a similarity between RRAM
devices and diodes.

(a)

(b)

(c)

Figure 2: (a) Pixel schematic. Cmr is the RRAM-introduced parasitic
capacitance that forms a capacitor divider with the physical capacitance Cb.
Q2-3 build a double-gated transistor. (b) RRAM-C branch equivalent concept
shows the memristor acting as a switch. (c) The arrangement of post-processed
RRAM in pixels. RRAM is placed at the top of the transistors and the
capacitors.

##  III System Overview

The system constructs a 64 x 64 CAM array with RRAM in-pixel, it is capable of
performing content addressable read, address addressable read, and write
operations.

###  III-A Pixel

Fig.2 shows the TCAM pixel schematic in this work. To maximize cell density,
only nMOS transistors are used. It has a 3T1R1C structure which consists of an
RRAM, a capacitor Cb, and three transistors. 1-bit of data is stored in the
RRAM represented by different resistive states. The dotted capacitance Cmr is
the parasitic capacitance introduced by the RRAM MIM structure, whose size is
determined by the area of the fabricated RRAM. The bottom capacitor Cb is
chosen as a Metal-Oxide-Metal (MOM) capacitor which uses inter-digitated
fingers, customized to a smaller minimum capacitor than the foundry’s standard
cells (in different technologies different choices of capacitor implementation
may be warranted). We highlight the physical, in-pixel RRAM position in fig.2
where the active device is placed above the CMOS metal layer. The graph only
shows the topmost CMOS metallisation layer of Cb for clarity. The pixel
transistors and other layers are hidden below this metal layer. The cross-
section view is obtained from the cut-line dissecting the top view. This RRAM
device has an area of 0.35 µm $\times$ 0.35 µm and its capacitance is
approximated to 2.2 fF based on measurements of physical RRAM devices.

The pixel supports three operations: content addressable read (CAR), address
addressable read (AAR), and write (WRT). The transistor Q1 is reused for both
WRT and AAR operations, whereas transistors Q2-3 are only activated for CAR.
RRAM LRS is defined at 112 k and HRS at 8.04 Mas they are reasonably easy to
achieve in our practical RRAM and for which we have specific, measured models
that we will be using throughout the rest of this work. The circuit is
operated with a primary 1.8V supply voltage VDD and an adjustable secondary
supply voltage VSEC, here designed to range within [1, 1.4] V. VSEC is applied
to cue/ $\overline{\text{cue}}$ and precharge signals only.

### Content Addressable Read

TABLE I: 3T1R1C voltage levels at different stages Cue | Stored data | RRAM | Vmid | Match-line
---|---|---|---|---
1 | 1 | HRS | Low | High
0 | LRS | High | Low
0 | 1 | HRS | High | Low
0 | LRS | Low | High
X | 1 | HRS | Low | High
0 | LRS | Low | High
Figure 3: CAR operation waveform for controlling searches and the
corresponding outputs at match-line when RRAM are at LRS and HRS. Figure 4:
(a) AAR equivalent schematic for activating circuit part that produces AAR
results. Pixels share the connection at psw node by accumulating charges at
the line capacitance, and the output is augmented by a latch comparator. (b)
AAR operation waveform with peripheral controlling input sequence and output
obtained at the latch comparator when RRAM is at LRS and HRS. (c) Equivalent
circuit schematic for the RRAM write operation and for the assisted ones that
help to maintain higher voltages over RRAM.

Content addressable search can be operated in parallel throughout the entire
array. The data one is searching for (the ”cue”), is input to cue and its
complementary data to $\overline{\text{cue}}$ in fig.2: when searching for a
’1’, we set cue to VSEC and $\overline{\text{cue}}$ to GND and vice versa for
a ’0’. Additionally, if both cue and $\overline{\text{cue}}$ are set to GND,
the system performs a ”don’t care” search (’X’). Q1 is turned off during the
entire search operation. The state of the RRAM modulates the effective
capacitive divider ratio by either by-passing Cmr or not. The divider mid-
point node ’mid’ directly drives the gate of Q2. This is illustrated by the
equivalent switched capacitor network shown in fig.2. When the RRAM is at HRS
in M, the RRAM behaves as an open switch, and the Cb-Cmr divider functions
normally. When the RRAM is at LRS, Vmid directly follows cue (in the limit).
In practice, because the LRS used is fairly high, we obtain effective
capacitive divider modulation by shifting the RRAM-Cmr RC constant. This is
especially important at high speeds (100s of MHz). At the same time, the
behavior of Vmid also depends on the cue/ $\overline{\text{cue}}$ values,
resulting in table I. When the cue does not match the stored data (’miss’),
Vmid goes high, Q2 activates and match-line ML discharges. This is, therefore,
an ’OR match-line’. This also explains why cue = $\overline{\text{cue}}$ = GND
yields ‘don’t care’. The match-line only stays high when every pixel in its
column registers no ’miss’.

Fig. 3 demonstrates the CAR sequence in detail for 3x successive search
operations. Before each search, sw is opened to clear any residual charges at
Vmid. Then the match-line ML is pre-charged by the signal pre (active low) to
the supply voltage level VSEC for 1x clock cycle. At the same time, cue and
$\overline{\text{cue}}$ start to rise for 2 ns according to the cue data. Vmid
starts to accumulate charges and its equivalent voltage exceeds the threshold
voltage of Q2 only when a mismatch between the input data and the stored data
is detected. Then, the signal en at the gate of Q3 is strobed when the value
of Vmid has stabilized sufficiently. Finally, voltage levels at the match-line
(ml) at the end of the phase indicate the comparison result. Multi-bit data
can be checked by chaining multiple pixels with the same match-line. Every bit
miss degrades the ml voltage level so that a percentage of hit/miss can also
be observed given sufficiently sensitive sensing circuitry although here we
restrict ourselves to binary answer detection.

### Address Addressable Read

To enable access to the data bit that is stored in the pixel, the 1T1R
structure (Q1 and RRAM) is activated and the other part of the pixel remains
off. The equivalent circuit for the AAR operation is highlighted in fig.4(a).
Both cue and $\overline{\text{cue}}$ are at GND. Net psw is connected to a
horizontal chain of pixels (in array configuration). In this construction, the
parasitic capacitance of the line on psw creates a charge tank to reflect the
equivalent charge level when RRAM is at different states. The voltage levels
at psw are reflected by latch comparators with a reference voltage Vref_AAR.
The operation waveform is shown in fig. 4(b). The psw is firstly cleared by
signal clr to open Q5. Next, a 1 ns strobing at the net sec sets psw to VSEC.
Finally, sw is strobed and allows the line capacitance to discharge depending
on the resistive state of the RRAM being read. Then the AAR results get
amplified at AAR_out. Only 1x column of the array is activated in this
configuration and sensing circuitry at the periphery determines the result.

Figure 5: Voltages and currents measured across the resistor sweeping from [10
to 100k] during write operations in the forward direction and reversed
direction.

(a)

(b)

(c)

(d)

Figure 6: (a) System block diagram with IO whose core and front-line
peripherals are fully customized. (b) Peripheral circuit for processing input
data cue switching between read modes and writing modes. (c) The fabricated
chip from the foundry without RRAM being post-processed. (d) Pixel layout
views. To improve visibility, the left shows the customized MOM capacitor
placed above the transistors, and the right shows the remaining metal routes
in the same pixel without the capacitor.

### Write Operation

The emerging RRAM device models used in this work assume electroforming-free
operation. Programming is carried out using pulses. Fig.4(c) shows the
activated pixel components for the write operation. To write the RRAM to its
desired state, cue and psw are the two terminals where the bias voltages are
applied. We define forward direct writing when a bias voltage is applied at
cue and psw is connected to GND. A reverse direction write is achieved by
setting psw to VDD and keeping cue grounded. After biasing, sw is pulsed
resulting in voltage applied across the RRAM. For a standard write operation,
$\overline{\text{cue}}$ is always kept at GND for both write directions.
However, with the placement of Cb, some system instantiations can be built to
boost the voltages between the devices given the right conditions, but it is
out of the scope of the present work.

In principle, the RRAM writing conditions would be found by solving divider
equations in each case. However, for simplicity, we sweep a linear resistor to
observe the equivalent static resistance (ESR) at the DC operating point
during the write operations. Fig. 5 provides the IV across the ESR in the
pixel in both forward and reverse directions during the write operations. The
power supply is set to 1.8V. The forward direction allows more electric
portions into the resistor as we have direct control of $V_{gs}$ but we get
the source-degeneration effect in the reversed direction.

###  III-B System

Fig.6 provides an overview of a 64 x 64 array of CAM pixels. Data is stored in
columns since match-lines are shared column-wise. Therefore, pre, en, and sw
also share column-wise so that the connected match-line can provide an
equivalent voltage level indicating comparison similarity. cue and
$\overline{\text{cue}}$ are connected horizontally. psw is also connected
horizontally to enable AAR operations for each row. In this way, the array can
detect 64 sets of data with a 64-bit length. To analyze the outcome of CAR and
AAR operations, two pMOS-type latch comparators are designed to resolve the
potentially very small gap between the ’all-hit’ and ’1-bit miss’ scenarios
for CAR and the resulting differences between HRS- and LRS-induced outcomes at
psw for AAR. cue is operated at the secondary adjustable power supply VSEC for
CAR operation but it requires reaching the primary power supply VDD for WRT
operations. Additionally, the signal at psw should be able to switch between
the multiple supply voltages and the ground under different operation
conditions. This is achieved via 3x transistors, with pri connecting to the
primary 1.8V supply and sec to VSEC. As for $\overline{\text{cue}}$, it
operates at VSEC for CAR but stays at the VDD or GND for the other operations.
The peripheral circuit for supplying cue is shown in fig. 6 where an
additional signal supsw is introduced to swap between the supplies. To enable
parallel CAR searching, each row is provided with its own peripheral circuits
and signal drivers so that the entire array can be activated at the same time.
These parts of the system are circled as front-line peripherals where they are
implemented in the majority of CAM systems.

At the back-line peripherals that are not common to all systems, the chip
receives inputs through a de-serializer, which splits the incoming information
into address, data, and instructions. The finite state machine recognizes this
and generates all control signals for the array. Those signals are gated by a
group of flip-flops for synchronization and then delivered to the drivers and
peripherals of the array. The outputs from CAR and AAR operations are sent to
their corresponding serializers and output to the chip. For this work, we
implemented an internal clock running at 875MHz to orchestrate the control
signals but the system is also capable of operating at lower clock speeds by
connecting to an external clock.

###  III-C Layout

The CAM array is implemented in 0.18um technology. Fig.6 shows the fabricated
chip that has been received from the foundry without in-house post-processing
RRAM placed. The chip has an area of 1163 um x 1109 um where the digital ASIC
area occupancy is not optimized. The pixel layout is given in fig.6 with a
dimension of 3.04 um x 3.875 um. The transistor Q2 and Q3 share one of the
terminals as a double-gated transistor. To visualize pixel layout in layers,
only the bottom customized MOM capacitor Cb and transistors in the pixel are
shown on the left of fig.6. The other routing layers are presented on the
right. The pixel area is limited by the area of the bottom customized MOM
capacitor Cb which uses most of the metal layers, excluding METAL 1 and METAL
2 layers. The area of Cb can be significantly decreased if more metal layers
are available at a more advanced technology node. The same-size capacitance
can be implemented by a smaller area so that the pixel limiting factor becomes
the size of the three transistors.

##  IV Measurements

Due to the development of RRAM post-processing, this design has a limited
number of metal layers available for routing. It also has a major impact on
the customized MOM capacitor Cb whose capacitance value can be greater if more
metal layers are used within the same area. Thus, the simulations in the work
are established with an additional bottom RRAM which is always in its pristine
state with large resistance in Mega or Giga Ohms. There is no fundamental
difference to the concept but it acts as an adjustment to the engineering
realities of our particular test run. This is implemented for a higher Cb to
enlarge the capacitive divider ratio for testing strategy. It brings
flexibility to altering Cb when testing the chip as this second RRAM can be
post-processed with different dimensions (different sizes of capacitance).

TABLE II: Functional test cases for finding gaps between all data hit (blue)
and worst-case 1-bit data miss (red).

Search (cue) | RRAM Resistance State (data)
---|---
64HRS | 64LRS | 63HRS+1LRS | 1HRS+63LRS
64HRS | Hit | Miss | Miss | Miss
64LRS | Miss | Hit | Miss | Miss
63HRS+1LRS | Miss | Miss | Hit | Miss
1HRS+63LRS | Miss | Miss | Miss | Hit

Figure 7: Match-line equivalent voltages with four groups of RRAM (data)
response to four types of searching (cue) (1) 64 HRS, (2) 64 LRS, (3) 63 HRS +
1 LRS, and (4) 1 HRS + 63 LRS. It reports a 36mV gap between the lowest data
hit and the highest data miss.

(a)

(b)

Figure 8: (a) Energy consumption per bit for 64-bit data under four test cases
to define the best and the worst searching scenario. The energy measurement
takes account of the core and logic peripherals in fig.6. (b) Energy
consumption breakdown for core and front-line peripherals.

###  IV-A Function

According to the system implementation, the functionality test for the CAM
array should be focused on the content searching of 64-bit data where 64
pixels share the same match-line. The match-line should be able to distinguish
between the worst-case 1-bit data miss and all data hit. The voltage
differences read at the match-line are used to set the correct reference
voltages for the latch comparator. 64-bit data has $2^{64}$ sets of
combinations. An accurate function should be able to discriminate all
combinations without adjusting the voltage reference of the latch comparator.
Therefore, four types of combinations of RRAM resistance states (data) are
considered: 1) 64 HRS 2) 64 LRS 3) 63 HRS + 1 LRS 4) 1 HRS + 63 LRS. At the
same time, the searching cue is also set to these four cases. Their
corresponding relations are listed in table II where all data hit (blue) and
worst-case 1-bit data miss (red) are highlighted. Each case reflects the
search result by output voltage levels at its match line. To identify hits
from any misses, the output voltage levels for all data hits must have higher
values than that for any worst-case 1-bit data miss. We define a threshold
voltage between the lowest voltage for all data hits and the highest voltage
for worst-case 1-bit data misses among the test cases in table II.

Fig.7 displays output voltages observed at match-line with the defined test
sets for 64-bit data when VSEC is at 1.18V. The graph shows four groups of
searching: 64 HRS (5-8ns), 64 LRS (11-14ns), 63 HRS + 1 LRS (17-20ns), and 1
HRS + 63 LRS (23-26ns), whose match-line is shared between 64 pixels. The
Match line voltages with the four groups of RRAM resistance state arrangements
reflect the results of the searches. For example, considering the blue trace,
where there are 64 HRS RRAM, the first search gives a data hit and generates
the highest equivalent voltage at 905.25 mV in the cue(1) search phase. This
RRAM trace also reaches an equivalent voltage of 869.07 mV at the third
search, representing a worst-case 1-bit data miss when searching for 63 HRS +
1 LRS. A single pixel has two scenarios of searching, looking for 1 or 0.
Therefore, it has HRS hits and LRS hits that result in unequal voltages at the
match line. The search cue (1) phase covers the 64 HRS hits and the worst-case
on one HRS miss when searching for 1, while the search cue (2) phase gives the
voltage levels at 64 LRS hits and the worst-case on an LRS miss when searching
for 0. On the other hand, the worst case for an LRS miss when it is mostly
searching for 1 is recorded in the search cue (3), and the search cue (4)
tests for the worst case that an HRS miss when it is mostly searching for 0.
With the pre-defined four cases, the system covers the full range of possible
outcomes that 64-bit data may produce. By obtaining the lowest data hit and
highest worst-case 1-bit data miss, this test indicates a gap of 36.18 mV
between data hit and miss. The reference voltage of the latch comparator is
then set at a threshold within the specified range to identify the results.

A positive equivalent voltage gap at the match-line represents a valid
operating window to cover the full range of 64-bit data. A higher gap can
release the constraints on readout peripherals. At the same time, this valid
gap can be calibrated by adjusting the secondary supply VSEC which controls
the voltage at mid directly. This mid voltage controls the gate of the
transistor to pull down the match-line. With this flexible secondary supply
voltage control, the circuit can adapt to speed, corners, and other operating
conditions, detailed in the later sections.

###  IV-B Energy

Energy consumption for this work is highly dependent on the RRAM resistive
states, the capacitance value of $C_{b}$, and the secondary supply voltage
VSEC. The RRAM resistive state determines the conductivity of the pixel that
is linked to the match-line pull-down strength. As for the capacitance, its
energy has a relation of $E=CV^{2}/2$ where the voltage is supplied from VSEC.
The system benefits from the capacitance structure where there is no direct
path in the pixel during operations and therefore both idling and operating
energy are cut to the minimum levels.

TABLE III: Pixel energy consumption during CAR operation measured in fJ. RRAM has LRS equal to $112k\Omega$ and HRS is $8.04M\Omega$. Search data | RRAM | PRE | EN | TOTAL
---|---|---|---|---
HRS | LRS | 3.05 | 5.82 | 8.87
HRS | 3.04 | 2.41 | 5.45
LRS | LRS | 3.47 | 4.08 | 7.55
HRS | 2.37 | 3.41 | 5.78

Table III summarized the energy consumption at the pixel level undertaken with
a 4 fF $C_{b}$. The circuit operated with a 1.8 V power supply but the input
data are at 1 V. The energy is breaking down into CAR operating phases, (PRE
for pre-charge match-line and EN for release charges to allow output
evaluation.) It is observed that the energy consumption is higher when the
RRAM resistive state is at LRS. The energy consumption per pixel reaches the
highest at the searching miss between HRS in searching data and LRS in RRAM in
pixel. This is because the match-line discharge transistor (Q2 in fig.2) is in
the most conductive scenario.

The pixels are tied to a 64x64 array and the energy consumption per match-line
per bit search for the four test cases is recorded in fig.8. It is observed
with a reduction of energy per bit when the pixels are tied to an array
structure and share the match line. The worst energy consumption is detected
at 4.69 fJ/bit when all the data (in 64 HRS) are different from the search cue
(in 64 LRS). A 1-bit miss in pixel creates a path to discharge the match-line
where the energy is consumed. Therefore, the best energy consumption cases
happen when the data (in 64 LRS) is the same as the search cue (in 64 LRS). At
the same time, it is observed that searching in LRS consumes less energy than
that in HRS. In other words, searching in LRS means supplying voltage from the
bottom capacitor $C_{b}$ end where the RRAM accesses energy indirectly.

The system (core and front-line peripherals) energy consumption breakdown in
Fig. 8 shows that the array core only consumes 5% of overall front-line energy
consumption, whereas the heavy drivers and peripheral circuits consume the
majority of energy. This is because the searching mechanism in this system
borrows energy from its peripherals to service the capacitors. It contrasts
with regular DC approaches, changing the distribution of power dissipation
between peripherals and the core.

###  IV-C Corners

To observe the search outcome, a wider gap between the all-bit hit and worst
case one-bit miss helps in releasing the stress of the readout circuit. In
another aspect, the wider gap means that more bits can be tied together to the
data. This maximum gap operating point can be adjusted by controlling the
adjustable secondary supply VSEC.

Figure 9: Corner analysis for the 64 x 64 array core with pre-charge
transistors, showing that the secondary power supply VSEC can be used to
compensate for the PVT variations. The x-axis is sampled in steps of 10mV.

With the PVT variation, the system reflects the effect at the mid node
equivalent voltages leading to a substantial difference at the maximum gap
operating point if the voltages are near the threshold voltage of transistors.
Fig.9 plots the output gaps measured under the five corners from ff to ss with
the variation of VSEC in 10 mV sweeping from [1, 1.35V]. The results show that
the maximum gap for ff corner is achieved when VSEC is at 1.05V and gives the
highest gap among the tests. At the ss corner, a 1.3V VSEC is required to
reach its maximum gap.

##  V Discussion

Table IV lists the energy consumption for various non-volatile TCAM designs
benchmark the design with a 10x10 array at 0.18um technology node in [21] and
the measurement for this work at the same technology node. Their energy per
bit search is recorded in fJ/bit-search. The 2T2R and the 4T2R design uses two
RRAMs and they require the RRAM to operate in three different resistive
states. It also sets stringent constraints to the RRAM that can operate with
these designs. As for the 3T1R design, the pixel requires a relatively low
resistance for LRS, otherwise, the pixel recovery time gets longer and
therefore the operating speed is limited. Its direct current path also
indicates a large amount of in-efficient energy consumption. In this work, the
charge domain content addressable memory does not have a direct current path
during searches which leads to a minimum energy consumption. At the same time,
it also functioned with address addressable read which is also a charge-
limited operation, albeit the charge limitation happens at the bit line level
and involves the design of the peripherals.

TABLE IV: Energy consumption for various TCAM designs in fJ/bit-search.

| 2T2R [22] | 3T1R [20] | 4T2R [21] | This work
---|---|---|---|---
Original node | 90 nm | 90 nm | 16 nm | 180 nm
Device | PCM | RRAM | RRAM | RRAM
Array Size | 64x512 | 64x64 | 36x250 | 64x64
RRAM(LRS/HRS) | 10k/1M/1G | 10k/1M | 10k/1M/1G | 112k/8M
Energy(search 0) | 7.8* | 985.3* | 19.4* | 3.33
Energy(search 1) | 12.2* | 1019.7* | 81.5* | 4.96
Mechanism | Two-bit | Resistive | Resistive | Capacitive
encoding | divider | divider | divider

*Dennard-normalized to 180 nm equivalent with 10x10 array in [21]

However, non-volatile CAM arrays are optimized with the non-volatile devices
that they are used, whose IV characteristics can directly impact the system’s
performance. It is unfair to define the energy measurement with pixel energy
only since the capacitive elements involve a flow of charge to its peripherals
and may lead to more energy consumption measured at the peripherals. On the
other hand, even testing with the same RRAM structure, the resistance value
can be treated as a high resistance state in one design but would be regarded
as a low resistance state in another circuit. The materials that are used to
form the device determine the parasitic capacitance of the device and further
affect the choice of the physical capacitor in this work. Both RRAM operating
resistance states and capacitance in pixel contribute to the major energy
consumption of the array core. Therefore, it brings challenges to comparing
the performances between CAM designs and the performance between different
RRAM models in the same design.

The designed CAM in this work can have 64 different data stored with a length
of 64-bit. The searching ability of the array in terms of the data length is
reflected by the length of the data chain (number of pixels in a column).
These pixels share a match-line and control the output gaps of the searched
results. More pixels make it harder to observe a difference between the lowest
all-bit match and the highest one-bit miss cases. When the gaps become too
small, an accurate sense amplifier that has high precision would required. At
the same time, the searching capacity on the amount of data sets is affected
by the pixels in a row which share the driver for each search cue. When more
pixels share the same driver, it means an increase in the driving strength as
the overall capacitance per row increases. The system operates by a sequence
of controls that involve switching activities. These switching activities are
directly linked to power consumption, especially for those large-sized drivers
and peripherals. When the scale of data becomes large, performance
optimization may target the way of sharing peripherals trade-off against
speed.

This work is implemented in 0.18um technology whose digital ASIC part occupies
at least three times greater than the RRAM CAM array. The system operating
frequency is limited by the technology rather than the circuit. With the
scaling of technology, the chip density would be increased and the digital
ASIC area could be shrunk. At the same time, the circuit can operated at a
higher speed. The RRAM is assumed to have an area of 0.35um x 0.35um whereas,
it can be fabricated with a smaller area of 0.1um x 0.1um, depending on the
fabrication equipment and conditions. The area reflects the device’s parasitic
capacitance and further determines the choice of the physical capacitance in
pixels as they form a capacitive divider. The secondary power supply VSEC
helps with compensating such variants in pixels and makes the pixels operate
in the correct voltage range.

Moreover, the system is insensitive to the operating frequency with the theory
of performing RRAM RS as an open or short circuit structure. In other words,
we define the LRS limit towards zero and the HRS limit towards infinite. In
the HRS cases, the infinite resistance made the circuit follow the capacitive
divider, while the LRS case made the circuit follow the input cue, where both
cases are frequency-independent.

Data centers are becoming unsustainably power-hungry, such energy-efficient
memory is beneficial to these systems with large databases with abilities to
search data in parallel. The implication of capacitance also brings
possibilities of recycling the flow of charges in capacitors for further
energy reduction.

##  VI Conclusion

In conclusion, this paper presents a 3T1R1C memristive-capacitive TCAM array
that uses RRAM as data storage and data comparison. This charge domain non-
volatile CAM design applies a physical capacitor to form a capacitive divider
with the RRAM parasitic capacitance, featuring no direct current paths and low
leakages. The operating mechanism on 64-bit data and the method for finding
its valid operating window are analyzed. The CAM supports both content
addressable read and address addressable read with charge-limited operations.
It reports an average energy of 64-bit data match at 1.71 fJ/bit-search and
4.69 fJ/bit-search for 64-bit data misses with an operating speed of 875MHz in
0.18um technology. With the continuing development of RRAM, we believe this
CAM can be part of mainstream memories for powering future databases in data
centers all around the world.

## Acknowledgment

This work has been supported by the Engineering and Physical Sciences Research
Council (EPSRC) grants EP/V008242/1,2 and EP/R024642/1,2.

## References

  * [1] R. Karam, R. Puri, S. Ghosh, and S. Bhunia, “Emerging trends in design and applications of memory-based computing and content-addressable memories,” _Proceedings of the IEEE_ , vol. 103, no. 8, pp. 1311–1330, 2015.
  * [2] A. Ooka, S. Atat, K. Inoue, and M. Murata, “Design of a high-speed content-centric-networking router using content addressable memory,” in _2014 IEEE conference on computer communications workshops (INFOCOM WKSHPS)_. IEEE, 2014, pp. 458–463.
  * [3] A. X. Liu, C. R. Meiners, and E. Torng, “Packet classification using binary content addressable memory,” _IEEE/ACM Transactions on Networking_ , vol. 24, no. 3, pp. 1295–1307, 2016.
  * [4] K. Ni, X. Yin, A. F. Laguna, S. Joshi, S. Duenkel, M. Trentzsch, J. Müller, S. Beyer, M. Niemier, X. S. Hu _et al._ , “Ferroelectric ternary content-addressable memory for one-shot learning,” _Nature Electronics_ , vol. 2, no. 11, pp. 521–529, 2019.
  * [5] S. Paul and S. Bhunia, “Reconfigurable computing using content addressable memory for improved performance and resource usage,” in _Proceedings of the 45th annual design automation conference_ , 2008, pp. 786–791.
  * [6] C. E. Graves, C. Li, X. Sheng, D. Miller, J. Ignowski, L. Kiyama, and J. P. Strachan, “In-memory computing with memristor content addressable memories for pattern matching,” _Advanced Materials_ , vol. 32, no. 37, p. 2003437, 2020.
  * [7] K.-J. Lin and C.-W. Wu, “A low-power cam design for lz data compression,” _IEEE transactions on Computers_ , vol. 49, no. 10, pp. 1139–1145, 2000.
  * [8] B.-D. Yang, Y.-K. Lee, S.-W. Sung, J.-J. Min, J.-M. Oh, and H.-J. Kang, “A low power content addressable memory using low swing search lines,” _IEEE Transactions on Circuits and Systems I: Regular Papers_ , vol. 58, no. 12, pp. 2849–2858, 2011.
  * [9] A. T. Do, C. Yin, K. S. Yeo, and T. T.-H. Kim, “Design of a power-efficient cam using automated background checking scheme for small match line swing,” in _2013 Proceedings of the ESSCIRC (ESSCIRC)_ , 2013, pp. 209–212.
  * [10] K. Pagiamtzis and A. Sheikholeslami, “Content-addressable memory (cam) circuits and architectures: A tutorial and survey,” _IEEE journal of solid-state circuits_ , vol. 41, no. 3, pp. 712–727, 2006.
  * [11] C.-S. Lin, J.-C. Chang, and B.-D. Liu, “A low-power precomputation-based fully parallel content-addressable memory,” _IEEE Journal of Solid-State Circuits_ , vol. 38, no. 4, pp. 654–662, 2003.
  * [12] T. Prodromakis, B. P. Peh, C. Papavassiliou, and C. Toumazou, “A versatile memristor model with nonlinear dopant kinetics,” _IEEE transactions on electron devices_ , vol. 58, no. 9, pp. 3099–3105, 2011.
  * [13] G. W. Burr, M. J. Breitwisch, M. Franceschini, D. Garetto, K. Gopalakrishnan, B. Jackson, B. Kurdi, C. Lam, L. A. Lastras, A. Padilla _et al._ , “Phase change memory technology,” _Journal of Vacuum Science & Technology B, Nanotechnology and Microelectronics: Materials, Processing, Measurement, and Phenomena_, vol. 28, no. 2, pp. 223–262, 2010.
  * [14] H.-T. Lue, C.-J. Wu, and T.-Y. Tseng, “Device modeling of ferroelectric memory field-effect transistor for the application of ferroelectric random access memory,” _IEEE transactions on ultrasonics, ferroelectrics, and frequency control_ , vol. 50, no. 1, pp. 5–14, 2003.
  * [15] X. Dong, X. Wu, G. Sun, Y. Xie, H. Li, and Y. Chen, “Circuit and microarchitecture evaluation of 3d stacking magnetic ram (mram) as a universal memory replacement,” in _2008 45th ACM/IEEE Design Automation Conference_. IEEE, 2008, pp. 554–559.
  * [16] R. Waser and M. Aono, “Nanoionics-based resistive switching memories,” _Nanoscience and Technology: A Collection of Reviews from Nature Journals_ , pp. 158–165, 2009.
  * [17] S. Stathopoulos, A. Khiat, M. Trapatseli, S. Cortese, A. Serb, I. Valov, and T. Prodromakis, “Multibit memory operation of metal-oxide bi-layer memristors,” _Scientific reports_ , vol. 7, no. 1, pp. 1–7, 2017.
  * [18] Y. Pan, P. Foster, A. Serb, and T. Prodromakis, “A rram-based associative memory cell,” in _2021 IEEE International Symposium on Circuits and Systems (ISCAS)_ , 2021, pp. 1–5.
  * [19] M.-F. Chang, L.-Y. Huang, W.-Z. Lin, Y.-N. Chiang, C.-C. Kuo, C.-H. Chuang, K.-H. Yang, H.-J. Tsai, T.-F. Chen, and S.-S. Sheu, “A reram-based 4t2r nonvolatile tcam using rc-filtered stress-decoupled scheme for frequent-off instant-on search engines used in iot and big-data processing,” _IEEE Journal of Solid-State Circuits_ , vol. 51, no. 11, pp. 2786–2798, 2016.
  * [20] M.-F. Chang, C.-C. Lin, A. Lee, Y.-N. Chiang, C.-C. Kuo, G.-H. Yang, H.-J. Tsai, T.-F. Chen, and S.-S. Sheu, “A 3t1r nonvolatile tcam using mlc reram for frequent-off instant-on filters in iot and big-data processing,” _IEEE Journal of Solid-State Circuits_ , vol. 52, no. 6, pp. 1664–1679, 2017.
  * [21] C. E. Graves, C. Li, X. Sheng, W. Ma, S. R. Chalamalasetti, D. Miller, J. S. Ignowski, B. Buchanan, L. Zheng, S.-T. Lam _et al._ , “Memristor tcams accelerate regular expression matching for network intrusion detection,” _IEEE Transactions on Nanotechnology_ , vol. 18, pp. 963–970, 2019.
  * [22] J. Li, R. K. Montoye, M. Ishii, and L. Chang, “1 mb 0.41 $\mu$m2 2t-2r cell nonvolatile tcam with two-bit encoding and clocked self-referenced sensing,” _IEEE Journal of Solid-State Circuits_ , vol. 49, no. 4, pp. 896–907, 2013.
  * [23] G. Yin, Y. Cai, J. Wu, Z. Duan, Z. Zhu, Y. Liu, Y. Wang, H. Yang, and X. Li, “Enabling lower-power charge-domain nonvolatile in-memory computing with ferroelectric fets,” _IEEE Transactions on Circuits and Systems II: Express Briefs_ , 2021.
  * [24] C. Li, C. E. Graves, X. Sheng, D. Miller, M. Foltin, G. Pedretti, and J. P. Strachan, “Analog content-addressable memories with memristors,” _Nature communications_ , vol. 11, no. 1, pp. 1–8, 2020.
  * [25] I. Messaris, A. Serb, S. Stathopoulos, A. Khiat, S. Nikolaidis, and T. Prodromakis, “A data-driven verilog-A ReRAM model,” _IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems_ , vol. 37, no. 12, pp. 3151–3162, 2018.
  * [26] T. Abbey, C. Giotis, A. Serb, S. Stathopoulos, and T. Prodromakis, “Thermal effects on initial volatile response and relaxation dynamics of resistive ram devices,” _IEEE Electron Device Letters_ , vol. 43, no. 3, pp. 386–389, 2022.

|  Yihan Pan (Graduate Student Member, IEEE) received her B.Eng. degree in
Electronic Engineering at the University of Manchester, U.K. in 2018 and her
M.Sc. degree in Analogue and Digital Integrated Circuit Design at Imperial
College London, U.K. in 2019. She is pursuing a Ph.D. degree at the Centre for
Electronics Frontiers, Institute for Integrated Micro and Nano Systems,
University of Edinburgh, U.K. Her research interests include hardware
topologies for symbolic processing and RRAM-based memory architectures.
---|---
|  Adrian Wheeldon (Member, IEEE) is a Research Associate at the Centre for
Electronics Frontiers, University of Edinburgh. He received the M.Eng. degree
in Electronic Engineering with Computer Systems from the University of
Southampton in 2016, and the Ph.D degree in Electronic Engineering from the
Newcastle University in 2022. Adrian has developed demonstrator hardware for
unconventional machine learning algorithms in both FPGA and ASIC. He has been
involved in 3 ASIC tapeouts, holds several patents and has published 10+
papers in the areas of machine learning, vector symbolic architecture and
digital circuit design.
---|---
|  Mohammed Mughal (Member, IEEE) is a Postdoctoral Research Associate at the
meLAB, James Watt School of Engineering, University of Glasgow. He holds his
Ph.D. and Postgraduate Diploma (PGD) from the University of Glasgow in 2017
and 2012 respectively. He worked as a KTP associate in flexible IC design,
research fellow, and research associate before joining meLAB. His research
interests include Analog and Mixed signal design, cryo-CMOS IC design for
quantum computing, image sensors, analog neuromorphic computing, and AI
hardware design.
---|---
|  Shady Agwa (Member, IEEE) is a Research Fellow at the Centre for
Electronics Frontiers CEF, The University of Edinburgh (UK). He received his
BSc and MSc degree from Assiut University (Egypt), both in Electrical
Engineering. He got his PhD in Electronics Engineering from The American
University in Cairo (Egypt) in 2018. Following his PhD, he joined the Computer
Systems Laboratory at Cornell University (USA) as a Postdoctoral Associate for
two years. In 2021, Shady joined the Centre for Electronics Frontiers at the
University of Southampton (UK) as a Senior Research Fellow and then as a
Research Fellow at the University of Edinburgh (UK). His research interests
span across VLSI and Computer Architecture using conventional and emerging
technologies for AI applications. His work focuses on unconventional ASIC-
Driven AI Architectures which cover In-Memory Computing, Stochastic Computing,
Systolic Arrays, Content-Addressable Memories, Beyond-Von Neumann
Architectures and Energy-Efficient Digital ASIC Design.
---|---
|  Themis Prodromakis (Senior Member, IEEE) received the bachelor’s degree in
electrical and electronic engineering from the University of Lincoln, U.K.,
the M.Sc. degree in microelectronics and telecommunications from the
University of Liverpool, U.K., and the Ph.D. degree in electrical and
electronic engineering from Imperial College London, U.K. He then held a
Corrigan Fellowship in nanoscale technology and science with the Centre for
Bio-Inspired Technology, Imperial College London, and a Lindemann Trust
Visiting Fellowship with the Department of Electrical Engineering and Computer
Sciences, University of California at Berkeley, USA. He was a Professor of
nanotechnology at the University of Southampton, U.K. He holds the Regius
Chair of Engineering at the University of Edinburgh and is Director of the
Centre for Electronics Frontiers. He is currently a Royal Academy of
Engineering Chair in emerging technologies and a Royal Society Industry
Fellowship. His background is in electron devices and nanofabrication
techniques. His current research interests include memristive technologies for
advanced computing architectures and biomedical applications. He is a fellow
of the Royal Society of Chemistry, the British Computer Society, the IET, and
the Institute of Physics.
---|---
|  Alexantrou Serb (Senior Member, IEEE) received the degree in biomedical
engineering and the Ph.D. degree in electrical and electronics engineering
from Imperial College in 2009 and 2013, respectively. He was a Research Fellow
at the Zepler Institute (ZI), University of Southampton, U.K. He joined
University of Edinburgh as a Reader in School of Engineering in 2022, where
his research interests are cognitive computing, neuroinspired engineering,
algorithms, and applications using RRAM, RRAM device modeling, and
instrumentation design.
---|---