opensource.google.com

Menu

JuMP: A modeling language for mathematical optimization

Monday, October 18, 2021

The JuMP logo.

As an author of the paper JuMP: A Modeling Language for Mathematical Optimization, I am honored to have recently received the Mathematical Optimization Society’s Beale—Orchard-Hays Prize, an academic award given once every three years for work in the area of computational mathematical optimization. The award, in fact, is about the open source software project JuMP, which I started with Iain Dunning and Joey Huchette while we were PhD students at MIT’s Operations Research Center almost nine years ago. The humbling milestone of the Beale—Orchard-Hays Prize seems like a good occasion to reflect on JuMP, how it has matured and grown as an independent community-driven project, and Google’s role in enabling me to serve as JuMP’s BDFL.

JuMP was created—in the classical open source fashion—to scratch an itch. As graduate students, we wanted a software package that would enable us to write down and solve optimization problems, especially constrained optimization problems like linear programming and integer programming problems. We wanted it to be not only easy, but also fast and powerful. At the time, one was faced with trade-offs between ease-of-use, speed, and flexibility. For example, optimization libraries in Python were user-friendly but introduced noticeable performance bottlenecks. Commercial software such as AMPL was efficient but hard to extend. Low-level interfaces in C or C++ introduced complexities that were distracting for teaching and academic research. We weren’t satisfied with these trade-offs, and began experimenting with a new programming language called Julia that promised to provide the best of both worlds.

Our early experiments showed that Julia was indeed capable of impressive performance. While similar libraries based on Python could be slower to construct the data structure describing the optimization problem than to solve it, our prototype of JuMP was competitive with state-of-the-art commercial libraries. This gave us confidence that JuMP could be useful for the community, and we made the initial public release in October 2013.

Since then, it’s been a real ride! The first JuMP developers workshop in 2017 attracted thirteen speakers from four continents; this year’s workshop featured 32 virtual talks. Of the 800+ citations to the award-winning paper, we were surprised to discover that that about 75% of them were from outside the fields of operations research or optimization itself; about 20% are in energy and power systems, another 20% are in control and engineering, and the remaining citations are spread across scientific applications, computer science, machine learning, and other fields. These figures speak to the role of optimization as a fundamental technology that can be applied almost anywhere. One example application using JuMP of which I’m perhaps most proud is a study by Sepulveda et al. on cost-effective ways to decarbonize the power grid. This study is cited both by Bill Gates in his new book, “How to Avoid a Climate Disaster,” and by Google’s methodologies and metrics framework for its goal of operating data centers and campuses entirely on carbon-free energy by 2030.

As JuMP’s core development team grew beyond MIT and its original creators graduated, it was important for JuMP to find a new home for its long-term sustainability. We were lucky to find NumFOCUS, a nonprofit organization supporting open source scientific software (of which Google is a corporate sponsor). As a Google employee, I have continued contributing code for JuMP, traveling to workshops, and serving in leadership roles thanks in no small part to Google’s generous open source policies and support from my team and management chain. Last year, I was granted the honorific of Benevolent Dictator for Life (BDFL). I plan to use this power judiciously and rarely, relying instead on JuMP’s strong culture of consensus-driven development.

As for the future, JuMP’s 1.0 release is near on the horizon, and I look forward to whatever comes next!

By Miles Lubin, Algorithms & Optimization Team, Google Research

Open Source in the 2021 Accelerate State of DevOps Report

Wednesday, September 22, 2021

To truly thrive, organizations need to adopt practices and capabilities that will lead them to performance improvements. Therefore, having access to data-driven insights and recommendations about the most effective and efficient ways to develop and deliver technology is critical. Over the past seven years, the DevOps Research and Assessment (DORA) has collected data from more than 32,000 industry professionals and used rigorous statistical analysis to deepen our understanding of the practices that lead to excellence in technology delivery and to powerful business outcomes.
 
One of the most valuable insights that has come from this research is the categorization of organizations on four different performance profiles (Elite, High, Medium, and Low) based on their performance on four software delivery metrics centered around throughput and stability - Deployment Frequency, Lead Time for Changes, Time to Restore Service and Change Failure Rate. We found that organizations that excel at these four metrics can be classified as elite performers while those that do not can be classified as low performers. See DevOps Research and Assessment (DORA) for a detailed description of these metrics and the different levels of organizational performance.

DevOps Research and Assessment (DORA) showing a detailed description of these metrics and the different levels of organizational performance

We have found that a number of technical capabilities are associated with improved continuous delivery performance. Our findings indicate that organizations that have incorporated loosely coupled architecture, continuous testing and integration, truck-based development, deployment automation, database change management, monitoring and observability and have leveraged open source technologies perform better than organizations that have not adopted these capabilities.

Now that you know a little bit about what DORA is and some of its key findings, let’s dive into whether the use of open source technologies within organizations impacts performance.

A quick Google search will yield hundreds (if not, thousands) of articles describing the myriad of ways organizations benefit from using open source software—faster innovation, higher quality products, stronger security, flexibility, ease of customization, etc. We know using open source software is the way to go, but until recently, we still had little empirical evidence demonstrating that its use is associated with improved organizational performance – until today.

This year, we surveyed 1,200 working professionals from a variety of industries around the globe about the factors that drive higher performance, including the use of open source software. Research from this year’s DORA report illustrates that low performing organizations have the highest use of proprietary software. In contrast, elite performers are 1.75 times more likely to make extensive use of open source components, libraries, and platforms. We also find that elite performers are 1.5 times more likely to have plans to expand their use of open source software compared to their low-performing counterparts. But, the question remains—does leveraging open source software impact an organization’s performance? Turns out the answer is, yes!

Our research also found that elite performers who meet their reliability targets are 2.4 times more likely to leverage open source technologies. We suspect that the original tenets of the open source movement of transparency and collaboration play a big role. Developers are less likely to waste time reinventing the wheel which allows them to spend more time innovating, they are able to leverage global talent instead of relying on the few people in their team or organization.

Technology transformations take time, effort, and resources. They also require organizations to make significant mental shifts. These shifts are easier when there is empirical evidence backing recommendations—organizations don’t have to take someone’s word for it, they can look at the data, look at the consistency of findings to know that success and improvement are in fact possible.

In addition to open source software, the 2021 Accelerate State of DevOps Report discusses a variety of capabilities and practices that drive performance. In the 2021 report, we also examined the effects of SRE best practices, the pandemic and burnout, the importance of quality documentation, and we revisited our exploration of leveraging the cloud. If you’d like to read the full report or any previous report, you can visit cloud.google.com/devops.


By Daniella Villalba and Dustin Smith, user Experience Researchers (Google Cloud, Google Cloud Platform)

Learn Kubernetes with Google: Join us live on October 6!

Tuesday, September 21, 2021

 

Graphic describing the Multi-cluster Services API functionalities

Kubernetes hasn’t stopped growing since it was released by Google as an open source project back in June 2014: from July 7, 2020 to a year later in 2021, there were 2,284 new contributors to the project1. And that’s not all: in 2020 alone, the Kubernetes project had 35 stable graduations2. These are 35 new features that are ready for production use in a Kubernetes environment. Looking at the CNCF Survey 2020, use of Kubernetes has increased to 83%, up from 78% in 2019. With these many new people joining the community, and the project gaining so much complexity: how can we make sure that Kubernetes remains accessible to everyone, including newcomers?

This is the question that inspired the creation of Learn Kubernetes with Google, a content program where we develop resources that explain how to make Kubernetes work best for you. At the Google Open Source Programs Office, we believe that increasing access for everyone starts by democratizing knowledge. This is why we started with a series of short videos that focus on specific Kubernetes topics, like the Gateway API, Migrating from Dockershim to Containerd, the Horizontal Pod Autoscaler, and many more topics!

Join us live

On October 6, 2021, we are launching a series of live events where you can interact live with Kubernetes experts from across the industry and ask questions—register now and join for free! “Think beyond the cluster: Multi-cluster support on Kubernetes” is a live panel that brings together the following experts:
  • Laura Lorenz - Software Engineer (Google) / Member of SIG Multicluster in the Kubernetes project
  • Tim Hockin - Software Engineer (Google) / Co-Chair of SIG Network in the Kubernetes project
  • Jeremy Olmsted-Thompson - Sr Staff software Engineer (Google) / Co-Chair of the SIG Multicluster in the Kubernetes project
  • Ricardo Rocha - Computing Engineer (CERN) / TOC Member at the CNCF
  • Paul Morie - Software Engineer (Apple) / Co-Chair of the SIG Multicluster in the Kubernetes project
Why is Multi-cluster support in Kubernetes important? Kubernetes has brought a unified method of managing applications and their infrastructure. Engineering your application to be a global service requires that you start thinking beyond a single cluster; yet, there are many challenges when deploying multiple clusters at a global scale. Multi-cluster has many advantages, it lets you minimize the latency and optimize it for the people consuming your application.

In this panel, we will review the history behind multi-cluster, why you should use it, how companies are deploying multi-cluster, and what are some efforts in upstream Kubernetes that are enabling it today. Check out the “Resources” tab on the event page to learn more about the Kubernetes MCS API and Join us on Oct 6!

By María Cruz, Program Manager – Google Open Source Programs Office

1 According to devstats

Kubernetes Community Annual Report 2020

Announcing HIBA: Host Identity Based Authorization for SSH

Monday, September 20, 2021

How do you manage SSH access to a fleet of hosts? While OpenSSH provides many methods from a simple password to the use of certificates, each of these on its own still presents challenges.

Let's start by clarifying the difference between Authentication and Authorization. The former is a way to prove you are the entity you claim to be. This is usually achieved by providing the secret password associated with your account or by signing a challenge proving you own the private key corresponding to a public key. Authorization is a way to decide whether an entity is allowed or not to access a resource—usually performed after Authentication happens.

Request ⇒ AuthenticateAuthorize ⇒ Result

Authorization with OpenSSH is typically done using one of the following:
  • The principal knows the password of the target role account on the host.
  • The principal's public key is present in the authorized_keys of the target role account on the host.
  • The principal's username is present in the authorized_users of the target role account on the host.
Transposing this into a real life example: the bouncer of the Foo bar asks for your ID and checks if the photo matches your face (authentication), then decides, based on whether your name is on the guest list, if you are allowed in or not (authorization).

All these methods require accessing the target host in order to update authorizations (the guest list) by either updating the password, or adding/removing authorized_(keys|users).

Note: OpenSSH's use of certificates provides an extra layer of authorization by requiring a Certificate Authority (CA) to trust the incoming public key. Short lived certificates provide a flexible on/off switch for globally authorizing an entity access to the targeted hosts, but they still don't solve the problem of per hosts authorization policies.

Introducing Hiba image
Introducing HIBA

HIBA is a layer on top of OpenSSH that aims at solving this problem:
  • Centralized policy for controlling per host authorization.
  • Hermetic authorization mechanism making it suitable for deep embedded applications or emergency situations.
Going back to our previous nightclub example: the certificate is your ID, and the signed challenge is your photo/face matching. HIBA would be the bouncer, except its decision is not based on a guest list, but rather on you presenting a valid access ticket.

HIBA achieves this by relying on OpenSSH and the certificate infrastructure.
  • Authorization decisions are made centrally by the CA.
  • Authorization is stored as a certificate extension signed by the CA.
  • Hosts trust the CA thanks to TrustedUserCAKeys sshd configuration option.
  • Hosts enforce the authorization policy presented with the certificate by relying on HIBA via the AuthorizedPrincipalsCommand sshd configuration option.

In more details

HIBA defines two extensions to SSH certificates:
  • The HIBA identity, attached to host certificates, lists properties defining this host. They will be used as criteria for granting access.
  • The HIBA grant, attached to user certificates, lists constraints that a host must match for access to be granted.
On the host side, the hiba-chk helper is responsible for decoding extensions from both the host and user certificates and deciding whether or not to grant access.

On the CA side, the HIBA policy defines a set of grants and a list of users allowed to request them. Users can now ask the CA for HIBA grants to be attached to their certificates. The CA will confirm eligibility based on the policy and sign the certificate after adding the requested HIBA grants.

The HIBA extension scheme is flexible by nature, and any type of constraint can be assigned to grants as long as they are also defined in the identity. The exact specifications can be found in the PROTOCOL.authorizations file. HIBA only defines a handful of reserved constraints that are described in the PROTOCOL.extensions file.

The HIBA source code implements hiba-chk for processing authorizations as well as a library (libhiba) and a CLI (hiba-gen) for generating HIBA extensions. It also provides a simple shell based CA implementation hiba-ca.sh.

Practical example

Hosts identities

Host identities example

Grants

Grants example

In this example:
  • A user with an Employee SEA grant can access any foo.bar hosts located in Seattle.
  • A user with the Guests grant can access foo.bar hosts everywhere, but only if they are Dance floor, while Celebrities can access both VIP lounge and Dance floor hosts.
  • The owner grant gives unrestricted access to any foo.bar hosts.
By Tristan Lelong – Site Reliability Enthusiast, Technical Infrastructure

Open source SystemVerilog tools in ASIC design

Thursday, September 16, 2021

Open source hardware is undeniably undergoing a renaissance whose origin can be traced to the establishment of RISC-V Foundation (later redubbed RISC-V International). The open ISA and ecosystem, in which Antmicro participated since the beginning as a Founding member, has sparked many open source CPU implementations, new tooling, methodologies, and trends which allow for more collaborative and software driven design.

Many of those broader open hardware activities have been finding a home in CHIPS Alliance, an open source organization we participate in as a Platinum member alongside Google, Intel, Western Digital, SiFive and others, whose goals explicitly encompass:
  • creating and maintaining open source ASIC and FPGA design tools (digital and analog)
  • open source core and uncore IP
  • interconnects, interoperability specs and more
This is in perfect alignment with Antmicro’s mission—as we’ve been heavily involved with many of the projects inside of and related to CHIPS providing commercial support, engineering services, and assistance in practical adoption for enterprise deployments.

As of this time, a range of everyday design, development, testing, and verification tasks are already possible using open source tools and components and are part of our and our customer’s everyday workflow. Other developments are within reach given a reasonable amount of development, which we can provide based on specific scenarios. Others still are much further away, but with dedicated efforts inside CHIPS in which we are involved together with partners like Google and Western Digital, there is a pathway towards a completely open hardware design and verification ecosystem. This will eventually unlock incredible potential in new design methodologies, vertical integration capabilities, and education and business opportunities. Until then, Antmicro can help you with extracting practical value for many scenarios such as simulation, linting, formatting, synthesis, continuous integration and more.

Building a SystemVerilog ecosystem in CHIPS

Some of the challenges towards practical adoption of open source in ASIC design have been related to the fact that a significant proportion of advanced ASIC design is done in SystemVerilog, a fairly complex and powerful language in its own right, which used to be poorly supported in the open source tooling ecosystem. Partial solutions like SystemVerilog to Verilog converters or paid plugins existed, but direct support lagged behind, making open source tools for SystemVerilog a difficult sell previously.

This has been fortunately changing rapidly with a dedicated development effort spearheaded by Google and Antmicro. Projects in this space include Verible, Surelog, UHDM and sv-tests that we have been developing, as well as integrating with existing tools like Yosys, Verilator under the umbrella of the SymbiFlow open source FPGA project, and which are now officially being transferred into the CHIPS Alliance to increase awareness and build a broader SystemVerilog ecosystem.

In this note, we will walk you through the state of the art in new SystemVerilog capabilities in open source projects, and invite you to reach out to see how CHIPS Alliance’s SystemVerilog projects can be useful to you today or in the near future.

A walk through the state of the art in new SystemVerilog capabilities in open source projects

Verible

The Verible project originated at Google; its main mission is to make SystemVerilog easily and quickly parsable for a wide variety of applications mostly focusing on developer tools.

Verible is a set of tools based on a common SystemVerilog parsing engine, providing a command line interface which makes integration with other tools for daily usage or CI systems for automatic testing and deployment a breeze.

Antmicro has been involved in the development of Verible since its initial open source release and we now provide a significant portion of current development efforts, helping adapt it for use in various open source projects or commercial environments that use SystemVerilog. One notable user is the security-focused OpenTitan project, which has driven many interesting developments and provides a good showcase of the capabilities being completely open source, well documented, fairly complex, and used in real applications.

Linter

One of the most common use cases for Verible is linting. The linter analyzes code for patterns and constructs that are deemed undesirable according to the implemented lint rules. The rules follow authoritative style guides that can be enforced on a project or company level in various SystemVerilog projects.

The rules range from simple ones like making sure the module name matches the file name to more sophisticated like checking variable naming conventions (all caps, snake case, specific prefix or suffix etc.) or making sure the labels after the begin and end statements match.

A full list of rules can be found in the Verible lint documentation and is constantly growing. Usage is very simple:

$ verible-verilog-lint --ruleset all core.sv 

core.sv:3:11: Interface names must use lower_snake_case naming convention and end with _if. [Style: interface-conventions] [interface-name-style]


The output of the linter is easy to understand, as the way issues are reported to the user is modeled after popular programming language compilers.

The linter is highly configurable. It is possible to select the rules for which the compliance will be checked, some rules allow for detailed configuration (e.g. max line length).

Rules can also be selectively waived in specific files or at specific lines or even by regex matching. In addition, some rules can be automatically fixed by the linter itself.

Formatter

The Verible formatter is a complementary tool for the linter. It is used to automatically detect various formatting issues like improper indentation or alignment. As opposed to the linter, it only detects and fixes issues that have no lexical impact on the source code.

The formatter also comes with useful helper scripts for selective and interactive reformatting (e.g. only format files that changed according to git, ask before applying changes to each chunk).

A toolset that consists of both the linter and the formatter can effectively remove all the discussions about styling, preferences and conventions from all pull requests. Developers can then focus solely on the technical aspects of the proposed changes.

$ cat sample.sv

typedef struct {

bit first;

        bit second;

bit

   third

        ;

  bit fourth;

bit fifth; bit sixth;

}

 foo_t;



$ verible-verilog-format sample.sv

typedef struct {

  bit first;

  bit second;

  bit third;

  bit fourth;

  bit fifth;

  bit sixth;

} foo_t;

Indexer

The Verible parser itself can be relatively easily used to perform many other tasks. One of the interesting use cases is generating a Kythe compatible indexing database.

Indexing a SystemVerilog project makes it very easy to collaborate on a project remotely. It is possible to navigate through the source code using nothing else than just a web browser.

The Kythe integration can be served on an arbitrary server, can be deployed after every commit in a project, etc. A showcase of the indexing mechanism can be found in our GitHub repository. The demo downloads the latest version of the Ibex core, indexes it, and deploys it to be viewed on a remote machine. The results can be viewed on the example index webpage.

The demo downloads the latest version of the Ibex core, indexes it, and deploys it to be viewed on a remote machine. The results can be viewed on the example index webpage.

Indexing is widely adopted for many larger open source software projects.

Thanks to Verible, it is now possible to do the same in the world of open source HDL designs, and of course private, company-wide deployments like this are also possible.

Surelog and UHDM

SystemVerilog is a powerful language but also complex. So far no open source tools have been able to support it in full. Implementing it separately for each project such as the Yosys synthesis tool or the Verilator simulator would take a colossal amount of time, and that’s where Surelog and UHDM come in.

Surelog, originally created and led by Alain Dargelas, aims to be a fully-featured SystemVerilog 2017 preprocessor, parser, and elaborator. It’s a modern tool and thus follows the current version of the SV standard without unnecessary deviations or legacy baggage.

What’s interesting is that Surelog is only a language frontend designed to integrate well with other tools—it outputs an elaborated design in an intermediate format called UHDM.

UHDM stands for Universal Hardware Data Model, and it’s both a file format for storing hardware designs and a library able to manipulate this format. A client application can access the data using VPI, which is a standard programming interface for SystemVerilog.

What this means is that the work required to create a SystemVerilog parser only needs to be done once, and other tools can use that parser via UHDM. This is much easier than implementing a full SystemVerilog parser within each tool. What’s more, any improvements in the unified parser will provide benefits for all client applications. Finally, any other parser is free to emit UHDM as well, so in the future we might see e.g. a UHDM backend for Verible.

Just like in Verible’s case, both Surelog and UHDM have recently been contributed into CHIPS Alliance to drive a broader adoption. We are actively contributing to both projects, especially around the integrations with tooling such as Yosys and Verilator, and practical use in open source and customer projects.

Recent Antmicro contributions adding UHDM frontends for Yosys and Verilator enabled Ibex synthesis and simulation. The complete OpenTitan project is the next milestone.

The Surelog/UHDM/Yosys flow enabling SystemVerilog synthesis without the necessity of converting the HDL code to Verilog is a great improvement for open source ASIC build flows such as OpenROAD’s OpenLane flow (which we also support commercially). Removing the code conversion step enables the developers to perform e.g. circuit equivalence validation to check the correctness of the design.

More information about Surelog/UHDM and Verible can be found in a dedicated CHIPS Alliance presentation that was recently given by Henner Zeller, Google’s Verible lead.

UVM is in the picture

No open source ASIC design toolkit can be complete without support for Universal Verification Methodology, or UVM, which is one of the most widespread verification methodologies for large-scale ASIC design. This has also been an underrepresented area in open source tooling and changing that is an enormous undertaking, but working together with our customers, most notably Western Digital, we have been making progress on that front as well.

Across the ASIC development landscape, UVM verification is currently performed with proprietary simulators, but a more easily distributable, collaborative and open ecosystem is needed to close the feedback loop between (emerging) open source design approaches and verification. Verilator is an extremely popular choice for other system development use cases but it has historically not focused on UVM-style verification. Other styles of verification, such as the very interesting and popular Python-based cocotb framework maintained by FOSSi Foundation, have been enabled in Verilator. But support for UVM, partly due to the size and complexity of the methodology, has been notably absent.

One of the features missing from Verilator but needed for UVM is SystemVerilog stratified scheduling, which is a set of rules specified in the standard that govern the way time progresses in a simulation, as well as the order of operations. A SystemVerilog simulation is divided into smaller steps called time slots, and each time slot is further divided into multiple regions. Specific events can only happen in certain regions, and some regions can reoccur in a single time slot.

Until recently, Verilator had implemented only a small subset of these rules, as all scheduling was being done at compilation time. Spearheading a long-standing development effort within CHIPS Alliance, in collaboration with the maintainer of Verilator, Wilson Snyder, we have built is a proof-of-concept version of Verilator with a dynamic scheduler, which manages the occurrence of certain events at runtime, extending the stratified scheduling support. More details can be found in Antmicro’s presentation for the inaugural CHIPS Alliance Deep Dive Cafe Talk.

Another feature required for UVM is constrained randomization, which allows generating random inputs to feed to a design in order to thoroughly test it. Unlike unconstrained randomization, which is already provided by Verilator, it allows the user to specify some rules for input generation, thus limiting the possible value space and making sure that the input makes sense. Work on adding this to Verilator has already started, although the feature is still in its infancy. There are many other features on the roadmap which will eventually enable practical UVM support—stay tuned with our CHIPS Alliance events to follow that development.

What next?

Support for SystemVerilog parsers, for the intermediate format, and for their respective backends and integrations with various tooling, as well as for UVM is now under heavy development. If you would like to see more effort put into a specific area, reach out to us at contact@antmicro.com. Antmicro offers commercial support services to extend the flows we’ve briefly presented here to various practical applications and designs, and to effectively integrate this approach into people’s workflows.

Adding to this our cloud expertise, Antmicro customers can benefit from a complete and industry-proven methodology scalable between teams and across on-premise and cloud installations, transforming chip design workflows to be more software-driven and collaborative. To take advantage of open source solutions with tools like Verilator, Yosys, OpenROAD and others - tell us about your use case and we will see what can be done today.

If you are interested in collaborating on the development of SystemVerilog-focused and other open hardware tooling, join CHIPS Alliance and participate in our workgroups and help us push innovation in ASIC design forward.

Originally posted on the Antmicro blog.

By guest author Michael Gielda, Antmicro, and Tim Ansell, Software Engineer
.