Cadence® system design and verification solutions, integrated under our System Development Suite, provide the simulation, acceleration, emulation, and management capabilities.
System Development Suite Related Products A-Z
Cadence® digital design and signoff solutions provide a fast path to design closure and better predictability, helping you meet your power, performance, and area (PPA) targets.
Full-Flow Digital Solution Related Products A-Z
Cadence® custom, analog, and RF design solutions can help you save time by automating many routine tasks, from block-level and mixed-signal simulation to routing and library characterization.
Overview Related Products A-Z
Driving efficiency and accuracy in advanced packaging, system planning, and multi-fabric interoperability, Cadence® package implementation products deliver the automation and accuracy.
Cadence® PCB design solutions enable shorter, more predictable design cycles with greater integration of component design and system-level simulation for a constraint-driven flow.
An open IP platform for you to customize your app-driven SoC design.
Comprehensive solutions and methodologies.
Helping you meet your broader business goals.
A global customer support infrastructure with around-the-clock help.
24/7 Support - Cadence Online Support
Locate the latest software updates, service request, technical documentation, solutions and more in your personalized environment.
Cadence offers various software services for download. This page describes our offerings, including the Allegro FREE Physical Viewer.
The Cadence Academic Network helps build strong relationships between academia and industry, and promotes the proliferation of leading-edge technologies and methodologies at universities renowned for their engineering and design excellence.
Participate in CDNLive
A huge knowledge exchange platform for academia to network with industry. We are looking for academic speakers to talk about their research to the industry attendees at the Academic Track at CDNLive EMEA and Silicon Valley.
Come & Meet Us @ Events
A huge knowledge exchange platform for academia. We are looking for academic speakers to talk about their research to industry attendees.
Americas University Software Program
Join the 250+ qualified Americas member universities who have already incorporated Cadence EDA software into their classrooms and academic research projects.
EMEA University Software Program
In EMEA, Cadence works with EUROPRACTICE to ensure cost-effective availability of our extensive electronic design automation (EDA) tools for non-commercial activities.
Apply Now For Jobs
If you are a recent college graduate or a student looking for internship. Visit our exclusive job search page for interns and recent college graduate jobs.
Cadence is a Great Place to do great work
Learn more about our internship program and visit our careers page to do meaningful work and make a great impact.
Get the most out of your investment in Cadence technologies through a wide range of training offerings.
Overview All Courses Asia Pacific EMEANorth America
Instructor-led training [ILT] are live classes that are offered in our state-of-the-art classrooms at our worldwide training centers, at your site, or as a Virtual classroom.
Online Training is delivered over the web to let you proceed at your own pace, anytime and anywhere.
Exchange ideas, news, technical information, and best practices.
The community is open to everyone, and to provide the most value, we require participants to follow our Community Guidelines that facilitate a quality exchange of ideas and information.
It's not all about the technlogy. Here we exchange ideas on the Cadence Academic Network and other subjects of general interest.
Cadence is a leading provider of system design tools, software, IP, and services.
Get email delivery of the Cadence blog featured here
(defun sumlist_2b (numbers)
(apply plus 0 0 numbers))
Unfortunately sumlist_2b cannot handle extremely long lists. In this posting, I will introduce sumlist_6 which does not suffer from this limitation.
This posting will not introduce any new SKILL++ primitives. Instead, it will use several primitives which have been introduced in the previous several postings to implement an algorithm which you may not have seen before. If any of these are unknown or mysterious to you, please consult previous postings of SKILL for the Skilled or the Virtuoso on-line documentation.
If you attempt to use sumlist_2b on extremely long lists it will fail. You can generate a very long list as follows:
data = (list 1.1 -2.1 2.3 -.04)
(for i 1 15
data = (append data data))
This produces a list of length 131072. If you attempt to sum this list with sumlist_2b you get the following error.
*Error* plus: too many arguments (at most 65535 expected, 131074 given) - (0 0 1.1 -2.1 2.3 ... )
<<< Stack Trace >>>
apply(plus 0 0 numbers)
The error message complains about a list of length 131074. This is because data has length 131072, but sumlist_2b prepends two additional 0's to the argument list. 131072 + 2 = 131074.
131072 + 2 = 131074
You may very well consider this an esoteric issue. And you would be right. If you are in charge of generating the data, and you know the number of elements in your list is less than 16K, then there is no need to worry about this corner case. I suspect very few of the readers of this blog have ever, or will ever encounter such a situation. Even with that being the case, I discuss this here in the hopes that some of the techniques may prove useful, even if the exact problem never occurs.
Another reason to present a solution to this particular problem is that in so doing we can combine several other concepts which have been discussed in the previous SKILL for the Skilled blog postings.
The following implementation of applyReduce takes advantage of (sstatus optimizeTailCall t) and unwindProtect as seen in a previous post of SKILL for the Skilled.
(sstatus optimizeTailCall t)
(defun applyReduce (fun args @key (maxArgs 8192) identity)
(labels ((apply_head (fun args tail)
(let ((save (cdr tail)))
(setcdr tail nil)
(apply fun args)
(setcdr tail save))))
(let ((tail (nthcdr (sub1 maxArgs) args)))
(if (cdr tail)
(apply_reduce (cons (apply_head fun args tail)
(apply fun args)))))
;; if args has more the two elements
(let ((save_optimizeTailCall (status optimizeTailCall)))
(sstatus optimizeTailCall t)
(sstatus optimizeTailCall save_optimizeTailCall))))
;; if args has exactly one element
;; if args is nil
The applyReduce function above calls the given function multiple times, but each time with a maximum of maxArgs number of arguments. The maxArgs parameter defaults to 8192 but you may override it to something smaller, especially to understand better how the function works.
(applyReduce plus '(.1 .2 .3 .4 .5 .6 .7 .8 .9
.11 .12 .13 .14 .15 .16 .17 .18 .19) ?maxArgs 5)
In the trace output you can see that the plus function is called several times, but never with more than 5 arguments. After the initial call, the first argument to plus is the return value of the previous call.
||||||||||||||(0.1 + 0.2 + 0.3 + 0.4 + 0.5)
||||||||||||||plus --> 1.5
||||||||||||||||(1.5 + 0.6 + 0.7 + 0.8 + 0.9)
||||||||||||||||plus --> 4.5
||||||||||||||||||(4.5 + 0.11 + 0.12 + 0.13 + 0.14)
||||||||||||||||||plus --> 5.0
||||||||||||||||||||(5.0 + 0.15 + 0.16 + 0.17 + 0.18)
||||||||||||||||||||plus --> 5.66
||||||||||||||||||(5.66 + 0.19)
||||||||||||||||||plus --> 5.85
Now we can use applyReduce to create an efficient sumlist_6 function which is able to add up the elements of an arbitrarily long list. We can use sumlist_6 to add up the 131072 elements of the list data created above.
(defun sumlist_6 (numbers)
(applyReduce plus numbers ?identity 0))
Testing it, we can see that it works and returns the correct result. We need to test sumlist_6 for a very long list, as well as for the nil list and a singleton list.
Recall the algorithm implemented as sumlist_1a.
(defun sumlist_1a (numbers)
(let ((sum 0))
(foreach number numbers
sum = sum + number)
On the Linux machine which I normally use, evaluating (sumlist_1a data) takes approximately 0.02 seconds, while evaluating (sumlist_6 data) takes about 0.003. I.e., sumlist_6 is about 6 times faster for large lists.
The technique shown in sumlist_2b is very simple, and requires very little code. Nevertheless, it has the caveat that it will fail for arbitrarily long lists. This usually does not matter, and because this corner case is relatively unlikely to occur, the technique is tempting to use, and in fact is a good solution if the data is under your control and you know the length of the list in question is not extremely large.
The technique shown in sumlist_6 is more correct, at the sacrifice of being more complicated code. That being said, because the complication of sumlist_6 is factored into the implementation of the function applyReduce, the actual implementation of sumlist_6 is as simple as sumlist_2b. I would suggest putting a copy of applyReduce in your personal SKILL function library, with the appropriate customer prefix of course.
In upcoming posts we'll continue to survey the SKILL++ language using the example of summing a list.
Previous blog posts in this series
SKILL for the Skilled: Many Ways to Sum a List (Part 5)
SKILL for the Skilled: Many Ways to Sum a List (Part 4)
SKILL for the Skilled: Many Ways to Sum a List (Part 3)
SKILL for the Skilled: Many Ways to Sum a List (Part 2)
SKILL for the Skilled: Many Ways to Sum a List (Part 1)